我可以代表大的整数在节点6只有幂没有依赖?
我正在研究要求a[0] ^ (a[1] ^ (a[2] ^ ... (a[n-1] ^ a[n])))
的最后一位的kata。 计算答案时, Math.pow
最终会超过Number.MAX_SAFE_INTEGER
,从而导致下面的modexp
返回错误的结果。
@ user2357112说,JS需要一个任意精度整数的库 ,这是一切都很好,但没有在kata表明这样的库是在远程环境,甚至我需要一个。
既然kata和SO在这个问题上指向不同的方向,我想知道我是否可以仅仅为了解决这个kata的目的来表示大整数而不用写整个库。
我正在进行的代码在下面,并且在打印不正确的结果之前通过了很多testing。 一些代码被省略以避免剧透。
TL; DR:如果我不能使用一个库,我可以做些什么来实际地代表Math.pow()所指示的用例的大整数?
function modexp(b, e) { let c = 1 while(e) { if (e & 1) c = c * b % 10 e >>= 1 b = b * b % 10 } return c; } function lastDigit(as) { if (!as || !as.length) return 1; let e = as.slice(1).reverse().reduce((p,c) => Math.pow(c,p)); return modexp(as[0], Number(e)); }
这显然是一个XY问题。 你不需要大整数。
你需要回到小学math。
什么是乘法? 那么让我们举一个例子:
警告:SPOILERS! 如果你想弄清楚自己,不要阅读以下内容!
1 2 x 2 3 ------ 3 6 last digit 6 2 4 ------ 2 7 6 notice how last digit is only involved in ONE multiplication operation?
嗯..似乎有一个模式。 让我们看看这种模式是否成立。 让我们乘以12 x 23 x 23
只做最后一个数字:
1 2 x 2 3 ------ 6 calculate ONLY last digit x 2 3 ------ 8 answer is: last digit is 8
让我们来看看我们的答案:
1 2 x 2 3 ------ 3 6 2 4 ------ 2 7 6 x 2 3 ------ 8 2 8 5 5 2 ------- 6 3 4 8 last digit is INDEED 8
所以看来你只能通过计算最后一位数字来find最后一位数字。 让我们试着实现一个powLastDigit()
函数。
警告:SPOILERS! 如果你想自己写,不要阅读代码!
function powLastDigit (number,power) { var x = number; for (var y=1; y<power; y++) { x = ((x%10)*(number%10))%10; // we only care about last digit! } return x; }
让我们来看看我们是否正确:
> powLastDigit(3,7) 7 > Math.pow(3,7) 2187 > powLastDigit(5,8) 5 > Math.pow(5,8) 390625 > powLastDigit(7,12) 1 > Math.pow(7,12) 13841287201
好。 看起来像在工作。 现在你可以使用这个function来解决你的问题。 它对于非常大的指数没有问题,因为它不处理大量的数字:
> powLastDigit(2323,123456789) 3
优化
上面的代码很慢,因为它使用一个循环。 可以通过使用Math.pow()
来加速它。 我会把这个留作家庭作业的问题。
我使用位数组来表示一个正整数;
[0,0,1,1] // bit array of 12 (MSB=rightmost)
这个结构是用来操纵总体指数E的
a[1] ^ (a[2] .. (a[n-1] ^ a[n])) // E
(!) LSD(a[0])
和整体指数E
之间有一个关系如下
//LSD(a[0]) LSD(LSD(a[0]) ^ E) for // [E/4R0, E/4R1, E/4R2, E/4R3] //--------- ---------------------------- // 0 [0, 0, 0, 0] // 1 [1, 1, 1, 1] // 2 [6, 2, 4, 8] // 3 [1, 3, 9, 7] // 4 [6, 4, 6, 4] // 5 [5, 5, 5, 5] // 6 [6, 6, 6, 6] // 7 [1, 7, 9, 3] // 8 [6, 8, 4, 2] // 9 [1, 9, 1, 9]
例如,find(2 ^(2 ^ 3))的最低有效位,
// LSD(a[0]) is 2 // E is 8 // implies E mod 4 is 0 // LSD(LSD(a[0]) ^ E) // for E/4R0 is 6 (ans)
为了确定E mod 4
,
E[0] + E[1] * 2 // the two LSBs
总之,我创build了一个数据结构,位数组来存储大整数,主要是指数部分的中间值。 位数组是dynamic长度最大值。 9007199254740991位,如果所有位都置位,则十进制值为2 ^(9007199254740991 + 1) – 1。此位数组永远不会转换回十进制(安全)。 总体指数E的唯一有趣的信息是它的两个最低有效位,它们是可以应用于上述关系(!)的E / 4的余数。
显然, Math.pow
不能用于位数组,所以我为它手工制作了一个简单的exp()
。 这是事实,这是微不足道的
//exponentiation == lots of multiplications == lots of additions //it is not difficult to implement addition on bit array
这只是演示上述想法的小提琴 。 如果E真的很大的话,它会变慢。 FYI
LSD.find([3,4,5,6]) // my Nightly hanged ~3s to find lsd
您可以通过子Bits.exp
,web工作者, Bits.exp
函数,simd等来优化Bits.exp
。祝你好运。
你不需要一个bigint库来解决这个kata。
你只对结果的最后一位感兴趣,幸运的是有一个权力属性可以帮助我们。 我们实际上需要计算模数为10的幂 。是的, 模幂运算在这里确实帮了我们一些忙,但是问题是指数也非常大 – 太大而无法计算,太大而无法运行一个循环迭代。 但我们不需要,我们感兴趣的是结果的模数。
有一种模式 ! 我们以4 ×为例:
x 4^x (4^x)%10 -------------------------- 0 4^0 = 1 1 1 4^1 = 4 4 2 4^2 = 16 6 3 4^3 = 64 4 4 4^4 = 256 6 5 4^5 = 1024 4 … … 20 4^20 = ??? 6 sic! 21 4^21 = ??? 4 … …
您将能够在所有模块化基础中find所有数字的这些模式。 它们都具有相同的特征:低于这个阈值,其余部分是不规则的,然后形成重复序列。 要按照这个顺序得到一个数字,我们只需要对指数进行模运算。
对于上面的例子( (4^x)%10
),我们使用查找表0 → 6, 1 → 4
并计算x % 2
; 门槛是1
。 在JavaScript代码中,它可能看起来像这样:
x < 1 ? 1 : [6, 4][x % 2];
当然, x
是由其余input的重复指数形成的非常大的数字,但是我们不需要将其整个计算 – 我们只想知道
- 无论是小于一个相对较小的数字(微不足道)
- 除以
q
之后的余数是什么 – 只是recursion调用我们正在实现的函数!