我可以代表大的整数在节点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调用我们正在实现的函数！