如何计算(a/b)％c，其中a，b和c是非常大的数字 [英] How to Calculate (a/b) %c where a,b and c are very large numbers

问题描述

我有一个功能
f(x)=(1^1)*(2^2)*(3^3)*.....(x^x) 我必须计算(f(x)/(f(x-r)*f(r)))modulo c
我可以计算f(x)和(f(x-r)* f(r)). 假设f(x)是一个 并且f(x-r)* f(r)是b. c是一个非常大的数字. `` 所以我怎么能计算(a/b)%c

I have a function
f(x)=(1^1)*(2^2)*(3^3)*.....(x^x) i have to calculate (f(x)/(f(x-r)*f(r)))modulo c
i can calculate f(x) and (f(x-r)*f(r)). assume f(x) is a and f(x-r)*f(r) is b. c is some number that is very larger. `` so i how can calculate (a/b)%c

推荐答案

1. 您的f(x)只是平方(PI累积乘法)的平方

1. your f(x) is just ᴨ (PI cumulative multiplication) squared

• 很难在这里写它，所以我将改为定义g(x0，x1)
• g(x0,x1)=x0*(x0+1)*(x0+2)*...*x1
• 如此:
• f(x)=g(1,x)^2

• it is hard to write it in here so i will deifine g(x0,x1) instead
• g(x0,x1)=x0*(x0+1)*(x0+2)*...*x1
• so:
• f(x)=g(1,x)^2

计算h(x,r,c)=f(x)/(f(x-r)*f(r))%c

• 将其重写为g()时，您会得到:
• h(x,r,c)=((g(1,x)/(g(1,x-r)*g(1,r)))^2)%c
• 现在要尽可能简化(并降低幅度)
• 因此最后计算sqr(不需要子结果)
• 摆脱重复的热量
• 有两个选项可以摆脱g(1,x-r)或g(1,r)
• 选择对您来说更好的选择，我会选择较大的一个
• 所以如果(x-r>r)则:
• h(x,r,c)=(g(x-r+1,x)/g(1,r)^2)%c
• 其他:
• h(x,r,c)=(g(r+1,x)/g(1,x-r)^2)%c

• when you rewrite it to g() you get:
• h(x,r,c)=((g(1,x)/(g(1,x-r)*g(1,r)))^2)%c
• now simplify (and lower magnitude) as much as you can
• so compute sqr as last (no need to have in sub-results)
• get rid of duplicate therms
• there are two options get rid of g(1,x-r) or g(1,r)
• choose what is better for you I would chose whichever is bigger
• so if (x-r>r) then:
• h(x,r,c)=(g(x-r+1,x)/g(1,r)^2)%c
• else:
• h(x,r,c)=(g(r+1,x)/g(1,x-r)^2)%c

一些数学调整

• 您应该同时计算两个热值a，b(来自(a/b)％c)
• 当两者都可以除以前几个素数中的任意一个，然后将其除以保持较低的幅度
• 类似的东西:
• `if((a& 1 == 0)&&(b& 1 == 0)){a >> = 1; b >> = 1; }//除以质数= 2 ...这通常就足够了
• 但是如果您的幅度很大，也许您应该添加一些像3,5,7，...
• 但是要始终衡量性能下降，如果下降太多，则停止

如果x大而r小

• 然后先计算b
• 在计算a
时
• 除了素数以外，还检查子结果​​是否也可以被b
整除.
• 如果将a除以b并将结果添加到最终除法结果中

• then compute b first
• and while computing a
• in addition to primes check also if the sub-result is divisible also by b
• if it is then divide a by b and add the result to the final division result

一些速度提升

• 您可以计算部分a,b
• 并且仅当展位的大小大于某个阈值时才开始测试可分性
• 您还可以让计算互相等待
• 所以如果a>1000000然后等到b也是如此大或整个
• ，并且在换向中也要这样做(如果b>100000 ....)
• 更大的阈值会带来更好的速度，但是您会受到整数实现的限制
• 如果使用bigints，则应使用较小的treshold，然后将基数的位数减半...

• you can compute partial a,b
• and start testing the divisibility only if booth have magnitudes bigger then some treshold
• also you can make the computation waiting for each other
• so if a>1000000 then wait until the b is also so big or whole
• and do the same also in revers (if b>100000 ....)
• the bigger treshold the better speed but you are limited by your integer implementation
• if using bigints then you should use treshold smaller then halve the bits of the base number ...

希望我没有犯一些愚蠢的数学错误...

Hope I did not make some silly math mistake...

这篇关于如何计算(a/b)％c，其中a，b和c是非常大的数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！