项目欧拉＃16 – C＃2.0
我一直在与C＃2.0中的Project Euler Problem＃16搏斗。 问题的关键在于你必须计算，然后迭代一个长度为604位（或那里）的数字中的每个数字。 然后，您将这些数字相加以产生答案。
这提出了一个问题：C＃2.0 没有可以处理这种计算精度的内置数据类型。 我可以使用第三方库 ，但这会破坏尝试以编程方式解决它而无需外部库的目的。 我可以在Perl中解决它; 但是我试图在C＃2.0中解决它（我将在下一次项目Euler问题的试运行中尝试使用C＃3.0）。
题
你有什么建议（ 不是答案！ ）来解决C＃2.0中的项目Euler＃16？ 有什么方法可行？
注意 ：如果您决定发布答案，请在尝试前添加一个在其前面写有### Spoiler的块引用。
一系列数字。 32位无符号整数是32位二进制数。 字符串“12345”是一系列5位数字。 数字可以以多种方式存储：作为位，字符，数组元素等。 C＃中具有完全精度的最大“本机”数据类型可能是十进制类型（128位，28-29位）。 只需选择您自己的数字存储方法，即可存储更大的数字。
至于其余部分，这会给你一个线索：
2 1 = 2
2 2 = 2 1 + 2 1
2 3 = 2 2 + 2 2
例：
The sum of digits of 2^100000 is 135178 Ran in 4875 ms The sum of digits of 2^10000 is 13561 Ran in 51 ms The sum of digits of 2^1000 is 1366 Ran in 2 ms SPOILER ALERT：C＃中的算法和解决方案如下。
基本上，提到一个数字只不过是一个数字数组。 这可以通过两种方式轻松表示：
- 作为一个字符串;
- 作为字符或数字的数组。
正如其他人所提到的，实际上建议以相反的顺序存储数字。 它使计算更容易。 我尝试了上述两种方法。 我发现字符串和字符算术很烦人（在C / C ++中它更容易;语法在C＃中简直令人讨厌）。
首先要注意的是，您可以使用一个数组执行此操作。 您不需要在每次迭代时分配更多存储空间。 如上所述，你可以通过将先前的2的幂加倍来找到2的幂。所以你可以通过加倍1千次来找到2 1000 。 可以使用通用算法完成加倍：
carry = 0 foreach digit in array sum = digit + digit + carry if sum > 10 then carry = 1 sum -= 10 else carry = 0 end if digit = sum end foreach
该算法与使用字符串或数组基本相同。 最后你只需加上数字。 一个简单的实现可能会在每次迭代时将结果添加到新数组或字符串中。 馊主意。 真的慢了下来。 如上所述，它可以在适当的位置完成。
但arrays应该有多大？ 那也很容易。 在数学上你可以转换2 ^ a到10 ^ f（a）其中f（a）是一个简单的对数转换，你需要的数字是从10的幂的下一个更高的整数。为简单起见，你可以使用：
digits required = ceil(power of 2 / 3)
这是一个近似和充分的。
你可以真正优化的地方是使用更大的数字。 一个32位有符号的int可以存储+/- 20亿之间的数字（大约。好9个数字等于10亿，所以你可以使用32位int（有符号或无符号）基本上是10亿“数字”。你可以工作你需要多少个int，创建那个数组，这就是运行整个算法所需的所有存储空间（130个字节），所有内容都已完成。
解决方案如下（相当粗略的C＃）：
static void problem16a() { const int limit = 1000; int ints = limit / 29; int[] number = new int[ints + 1]; number[0] = 2; for (int i = 2; i <= limit; i++) { doubleNumber(number); } String text = NumberToString(number); Console.WriteLine(text); Console.WriteLine("The sum of digits of 2^" + limit + " is " + sumDigits(text)); } static void doubleNumber(int[] n) { int carry = 0; for (int i = 0; i < n.Length; i++) { n[i] <<= 1; n[i] += carry; if (n[i] >= 1000000000) { carry = 1; n[i] -= 1000000000; } else { carry = 0; } } } static String NumberToString(int[] n) { int i = n.Length; while (i > 0 && n[--i] == 0) ; String ret = "" + n[i--]; while (i >= 0) { ret += String.Format("{0:000000000}", n[i--]); } return ret; }
我使用C＃解决了这个问题，当我发现Python可以在一个简单的操作中执行此操作时，令我感到沮丧。
您的目标是使用int值数组创建添加计算机。
掠夺者跟随
我最终使用了一个int值数组来模拟一个添加机器，但我向后表示了数字 – 你可以这样做，因为问题只是要求数字的总和，这意味着顺序是无关紧要的。
你实际上在做的是将值加倍1000倍，这样你就可以将存储在数组第一个元素中的值1加倍，然后继续循环，直到你的值超过10.这是你必须跟踪的地方持有价值。 超过10的2的第一个幂是16，因此第5次迭代后数组中的元素是6和1。
现在当你从第一个值（6）开始循环数组时，它变为12（所以你保留最后一个数字，并在数组的下一个索引上设置一个进位） – 当该值加倍时，你得到2 …加上1表示进位位等于3.现在你的数组中有2和3代表32。
继续这个过程1000次，你将有一个大约600个元素的数组，你可以很容易地添加。
假装你很年轻，用方纸。 对我来说，这就像一个数字列表。 然后将它加倍，你将每个数字加倍，然后通过减去10并将1添加到下一个索引来处理任何“进位”。 所以如果答案是1366 ……就像（完全没有优化，rot13）：
hfvat Flfgrz; hfvat Flfgrz.Pbyyrpgvbaf.Trarevp; pynff Cebtenz { fgngvp ibvq Pneel(Yvfg yvfg, vag vaqrk) { juvyr (yvfg[vaqrk] > 9) { yvfg[vaqrk] -= 10; vs (vaqrk == yvfg.Pbhag - 1) yvfg.Nqq(1); ryfr yvfg[vaqrk + 1]++; } } fgngvp ibvq Znva() { ine qvtvgf = arj Yvfg { 1 }; // 2^0 sbe (vag cbjre = 1; cbjre <= 1000; cbjre++) { sbe (vag qvtvg = 0; qvtvg < qvtvgf.Pbhag; qvtvg++) { qvtvgf[qvtvg] *= 2; } sbe (vag qvtvg = 0; qvtvg < qvtvgf.Pbhag; qvtvg++) { Pneel(qvtvgf, qvtvg); } } qvtvgf.Erirefr(); sbernpu (vag v va qvtvgf) { Pbafbyr.Jevgr(v); } Pbafbyr.JevgrYvar(); vag fhz = 0; sbernpu (vag v va qvtvgf) fhz += v; Pbafbyr.Jevgr("fhz: "); Pbafbyr.JevgrYvar(fhz); } }
我之前已经解决了这个问题，现在我用C＃3.0重新解决了这个问题。 🙂
我刚刚写了一个Multiply扩展方法，它接受一个IEnumerable和一个乘数，并返回一个IEnumerable 。 （每个int表示一个数字，第一个表示最不重要的数字。）然后，我只创建了一个包含项{1}的列表，并将其乘以2 1000次。 使用Sum扩展方法添加列表中的项目很简单。
19行代码，运行时间为13毫秒。 在我的笔记本上。 🙂
如果你想在C＃中进行初步计算，你需要某种大整数实现（就像gmp for C / C ++）。 编程是关于使用正确的工具来完成正确的工作。 如果你找不到一个好的C＃大整数库，那么用Python这样已经能够计算大数的语言来计算数字并不符合规则。 然后，您可以通过您选择的方法将此数字放入C＃程序，并迭代数字中的每个字符（您必须将其存储为字符串）。 对于每个字符，将其转换为整数并将其添加到总数中，直到达到数字的末尾。 如果你想要大整数，我用下面的python计算它。 答案是进一步下降。
部分剧透
10715086071862673209484250490600018105614048117055336074437503883703510511249361 22493198378815695858127594672917553146825187145285692314043598457757469857480393 45677748242309854210746050623711418779541821530464749835819412673987675591655439 46077062914571196477686542167660429831652624386837205668069376
扰流板下面！
>>> val = str(2**1000) >>> total = 0 >>> for i in range(0,len(val)): total += int(val[i]) >>> print total 1366
如果你有ruby，你可以很容易地计算出“2 ** 1000”并将其作为一个字符串。 应该是在C＃中轻松剪切/粘贴到字符串中。
扰流板
在Ruby中：（2 ** 1000）.to_s.split（//）.injection（0）{| x，y | X + y.to_i}
扰流板
如果你想看到解决方案，请查看我的其他答案 。 这是Java，但很容易移植到C＃
这是一个线索：
用列表表示每个数字。 这样你可以做基本的总和，如：
[1,2,3,4,5,6] + [4,5] _____________ [1,2,3,5,0,1]
将数字表示为整数序列的一种替代方案是将数字基数2 ^ 32表示为32位整数的列表，这是许多大整数库所做的。 然后，您必须将数字转换为基数10以进行输出。 这对于这个特殊的问题并没有太大的帮助 – 你可以直接写2 ^ 1000，然后必须除以10倍，而不是将2乘以1000倍（或者，因为1000是0b1111101000。计算产品的2 ^ 8,32,64,128,256,512使用重复平方2 ^ 8 =（（（2 ^ 2）^ 2）^ 2）））这需要更多空间和乘法，但操作要少得多） – 更接近正常大整数使用，因此您可能会发现它在以后的问题中更有用（如果您尝试使用digit-per int方法计算最后十位数字28433×2 ^（7830457）+1并重复添加，可能需要一些时间（虽然在这种情况下你可以使用modulo arthimetic，而不是添加数百万的数字字符串））。
我在这里发布的工作解决方案： http ： //www.mycoding.net/2012/01/solution-to-project-euler-problem-16/
代码：
import java.math.BigInteger; public class Euler16 { public static void main(String[] args) { int power = 1; BigInteger expo = new BigInteger("2"); BigInteger num = new BigInteger("2"); while(power < 1000){ expo = expo.multiply(num); power++; } System.out.println(expo); //Printing the value of 2^1000 int sum = 0; char[] expoarr = expo.toString().toCharArray(); int max_count = expoarr.length; int count = 0; while(count
欧拉问题＃16已在这里多次讨论，但我找不到能够很好地概述可能的解决方案方法的答案，即土地的原貌。 这是我试图纠正这一点。
本概述适用于已经找到解决方案并希望获得更完整图片的用户。 即使示例代码是C＃，它基本上与语言无关。 C＃2.0中没有一些function可用，但它们并不是必不可少的 – 它们的目的只是为了让枯燥的东西尽量少用。
除了使用现成的BigInteger库（不计算在内）之外，Euler＃16的简单解决方案分为两个基本类别：本地执行计算 – 即在2的幂的基础上 – 并按顺序转换为十进制获取数字，或直接在十进制基数中执行计算，以便数字可用而无需任何转换。
对于后者，有两个相当简单的选择：
- 反复加倍
- 通过反复平方来提供动力
原生计算+基数转换
这种方法最简单，其性能超过了使用.Net的内置BigInteger类型的天真解决方案。
实际的计算很简单：通过存储1000个二进制零并附加单个二进制1来执行1 << 1000的道德等价。
转换也非常简单，可以通过编写铅笔和纸分割方法来完成，并提供适当大的“数字”选择以提高效率。 中间结果的变量需要能够保持两个“数字”; 将long为1的十进制数除以最大元数位的9位小数（或“肢”，因为它通常在bignum传说中调用）。
class E16_RadixConversion { const int BITS_PER_WORD = sizeof(uint) * 8; const uint RADIX = 1000000000; // == 10^9 public static int digit_sum_for_power_of_2 (int exponent) { var dec = new List(); var bin = new uint[(exponent + BITS_PER_WORD) / BITS_PER_WORD]; int top = bin.Length - 1; bin[top] = 1u << (exponent % BITS_PER_WORD); while (top >= 0) { ulong rest = 0; for (int i = top; i >= 0; --i) { ulong temp = (rest << BITS_PER_WORD) | bin[i]; ulong quot = temp / RADIX; // x64 uses MUL (sometimes), x86 calls a helper function rest = temp - quot * RADIX; bin[i] = (uint)quot; } dec.Add((int)rest); if (bin[top] == 0) --top; } return E16_Common.digit_sum(dec); } }
我写了(rest << BITS_PER_WORD) | big[i] (rest << BITS_PER_WORD) | big[i]而不是使用operator +，因为这正是这里所需要的; 不需要进行带有进位传播的64位加法。 这意味着两个操作数可以直接写入寄存器对中的单独寄存器，也可以写入等效结构中的字段，如LARGE_INTEGER 。
在32位系统上，64位除法不能作为一些CPU指令内联，因为编译器无法知道算法保证商和余数适合32位寄存器。 因此，编译器调用可以处理所有可能性的辅助函数。
这些系统可以从使用较小的肢体中获益，即RADIX = 10000并且uint而不是ulong用于保持中间（双肢）结果。 C / C ++等语言的另一种选择是调用一个合适的编译器内部函数，它将原始的32位包装为32位到64位的乘法（假设用常数基数除法是通过与反函数相乘来实现的） 。 相反，在64位系统上，如果编译器提供合适的64×64到128位乘法原语或允许内联汇编程序，则肢体大小可以增加到19位。
十进制加倍
反复加倍似乎是每个人的最爱，所以让我们接下来做。 中间结果的变量需要保持一个'数字'加一个进位，每个肢long 18个数字。 去ulong不能改进东西（缺少0.04位到19位加上进位），所以我们不妨坚持下去。
在二进制计算机上，十进制分支与计算机字边界不一致。 这使得有必要在计算的每个步骤期间对肢体执行模运算。 这里，该模运算可以在进位的情况下减少到模数的减法，这比执行除法更快。 内部循环中的分支可以通过钻头来消除，但是对于基本算法的演示而言这将是不必要的模糊。
class E16_DecimalDoubling { const int DIGITS_PER_LIMB = 18; // == floor(log10(2) * (63 - 1)), b/o carry const long LIMB_MODULUS = 1000000000000000000L; // == 10^18 public static int digit_sum_for_power_of_2 (int power_of_2) { Trace.Assert(power_of_2 > 0); int total_digits = (int)Math.Ceiling(Math.Log10(2) * power_of_2); int total_limbs = (total_digits + DIGITS_PER_LIMB - 1) / DIGITS_PER_LIMB; var a = new long[total_limbs]; int limbs = 1; a[0] = 2; for (int i = 1; i < power_of_2; ++i) { int carry = 0; for (int j = 0; j < limbs; ++j) { long new_limb = (a[j] << 1) | carry; carry = 0; if (new_limb >= LIMB_MODULUS) { new_limb -= LIMB_MODULUS; carry = 1; } a[j] = new_limb; } if (carry != 0) { a[limbs++] = carry; } } return E16_Common.digit_sum(a); } }
这和基数转换一样简单，但除非是非常小的指数，它也不能在任何地方执行（尽管它有18个小数位的巨大元数字）。 原因是代码必须执行（指数-1）倍增，并且每次通过中完成的工作对应于总位数（肢数）的大约一半。
反复平方
通过重复平方提供动力背后的想法是用少量乘法替换大量的倍增。
1000 = 2^3 + 2^5 + 2^6 + 2^7 + 2^8 + 2^9 x^1000 = x^(2^3 + 2^5 + 2^6 + 2^7 + 2^8 + 2^9) x^1000 = x^2^3 * x^2^5 * x^2^6 * x^2^7 * x^2*8 * x^2^9
x ^ 2 ^ 3可以通过平方x三次，x ^ 2 ^ 5平方五次获得，等等。 在二进制计算机上，指数分解为2的幂很容易获得，因为它是表示该数字的位模式。 但是，即使非二进制计算机也应该能够测试数字是奇数还是偶数，或者将数字除以2。
乘法可以通过编写铅笔纸方法来完成; 这里我使用的辅助函数计算产品的一行，并将其添加到适当移位的结果中，这样部分产品的行不需要存储，以便稍后单独添加。 计算过程中的中间值最大可达两个“数字”，因此肢体只能是重复加倍的一半（除了“数字”之外只需要一个额外的位）。
注意：计算的基数不是2的幂，因此这里的简单移位无法计算2的方形。 从积极的方面来说，代码可以用于计算2以外的基数的幂。
class E16_DecimalSquaring { const int DIGITS_PER_LIMB = 9; // language limit 18, half needed for holding the carry const int LIMB_MODULUS = 1000000000; public static int digit_sum_for_power_of_2 (int e) { Trace.Assert(e > 0); int total_digits = (int)Math.Ceiling(Math.Log10(2) * e); int total_limbs = (total_digits + DIGITS_PER_LIMB - 1) / DIGITS_PER_LIMB; var squared_power = new List(total_limbs) { 2 }; var result = new List (total_limbs); result.Add((e & 1) == 0 ? 1 : 2); while ((e >>= 1) != 0) { squared_power = multiply(squared_power, squared_power); if ((e & 1) == 1) result = multiply(result, squared_power); } return E16_Common.digit_sum(result); } static List multiply (List lhs, List rhs) { var result = new List (lhs.Count + rhs.Count); resize_to_capacity(result); for (int i = 0; i < rhs.Count; ++i) addmul_1(result, i, lhs, rhs[i]); trim_leading_zero_limbs(result); return result; } static void addmul_1 (List result, int offset, List multiplicand, int multiplier) { // it is assumed that the caller has sized `result` appropriately before calling this primitive Trace.Assert(result.Count >= offset + multiplicand.Count + 1); long carry = 0; foreach (long limb in multiplicand) { long temp = result[offset] + limb * multiplier + carry; carry = temp / LIMB_MODULUS; result[offset++] = (int)(temp - carry * LIMB_MODULUS); } while (carry != 0) { long final_temp = result[offset] + carry; carry = final_temp / LIMB_MODULUS; result[offset++] = (int)(final_temp - carry * LIMB_MODULUS); } } static void resize_to_capacity (List operand) { operand.AddRange(Enumerable.Repeat(0, operand.Capacity - operand.Count)); } static void trim_leading_zero_limbs (List operand) { int i = operand.Count; while (i > 1 && operand[i - 1] == 0) --i; operand.RemoveRange(i, operand.Count - i); } }
这种方法的效率大致与基数转换相当，但这里有一些具体的改进。 通过编写一个特殊的平方例程可以加倍平方效率，该例程利用ai*bj == aj*bi的事实，如果a == b ，它将乘法的数量减半。
此外，存在用于计算加法链的方法，其涉及比使用指数位来确定平方/乘法时间表更少的操作。
助手代码和基准
由示例代码生成的元数字（十进制分支）中的十进制数字求和的辅助代码是微不足道的，但为了方便起见，我仍然在这里发布它：
internal class E16_Common { internal static int digit_sum (int limb) { int sum = 0; for ( ; limb > 0; limb /= 10) sum += limb % 10; return sum; } internal static int digit_sum (long limb) { const int M1E9 = 1000000000; return digit_sum((int)(limb / M1E9)) + digit_sum((int)(limb % M1E9)); } internal static int digit_sum (IEnumerable limbs) { return limbs.Aggregate(0, (sum, limb) => sum + digit_sum(limb)); } internal static int digit_sum (IEnumerable limbs) { return limbs.Select((limb) => digit_sum(limb)).Sum(); } }
这可以通过各种方式提高效率，但总体而言并不重要。
所有三个解都需要O（n ^ 2）时间，其中n是指数。 换句话说，当指数增长十倍时，它们将花费一百倍的时间。 通过采用分治策略，基数转换和重复平方都可以改善到大约O（n log n）; 我怀疑双重计划是否可以在类似的方面得到改善，但从那时开始就没有竞争力。
这里给出的所有三个解决方案都可用于打印实际结果，方法是使用合适的填充字符串化元数据并将它们连接起来。 我将函数编码为返回数字和而不是带有十进制分支的数组/列表，以便保持示例代码简单并确保所有函数具有相同的签名，以进行基准测试。
在这些基准测试中，.Net BigInteger类型包含如下：
static int digit_sum_via_BigInteger (int power_of_2) { return System.Numerics.BigInteger.Pow(2, power_of_2) .ToString() .ToCharArray() .Select((c) => (int)c - '0') .Sum(); }
最后，C＃代码的基准：
# testing decimal doubling ... 1000: 1366 in 0,052 ms 10000: 13561 in 3,485 ms 100000: 135178 in 339,530 ms 1000000: 1351546 in 33.505,348 ms # testing decimal squaring ... 1000: 1366 in 0,023 ms 10000: 13561 in 0,299 ms 100000: 135178 in 24,610 ms 1000000: 1351546 in 2.612,480 ms # testing radix conversion ... 1000: 1366 in 0,018 ms 10000: 13561 in 0,619 ms 100000: 135178 in 60,618 ms 1000000: 1351546 in 5.944,242 ms # testing BigInteger + LINQ ... 1000: 1366 in 0,021 ms 10000: 13561 in 0,737 ms 100000: 135178 in 69,331 ms 1000000: 1351546 in 6.723,880 ms
如您所见，基数转换几乎与使用内置BigInteger类的解决方案一样慢。 原因是运行时属于较新类型，它仅对有符号整数类型执行某些标准优化，但对无符号整数类型执行某些标准优化（此处：通过常量实现除法与反向相乘）。
我还没有找到一种检查现有.Net程序集的本机代码的简单方法，所以我决定使用不同的调查路径：我编写了一个E16_RadixConversion的变体进行比较，其中ulong和uint分别被long和int替换，并且BITS_PER_WORD减少1。 以下是时间安排：
# testing radix conv Int63 ... 1000: 1366 in 0,004 ms 10000: 13561 in 0,202 ms 100000: 135178 in 18,414 ms 1000000: 1351546 in 1.834,305 ms
比使用无符号类型的版本快三倍！ 编译器中有明确的麻木证据......
为了展示不同肢体大小的影响，我将C ++中的解决方案模板化为用作肢体的无符号整数类型。 时间以肢体的字节大小和肢体中的小数位数为前缀，用冒号分隔。 对于经常出现的操作字符串中的数字字符的情况没有时间，但可以肯定地说，这样的代码至少需要两倍于在字节大小的肢体中使用两位数的代码。
# E16_DecimalDoubling [1:02] e = 1000 -> 1366 0.308 ms [2:04] e = 1000 -> 1366 0.152 ms [4:09] e = 1000 -> 1366 0.070 ms [8:18] e = 1000 -> 1366 0.071 ms [1:02] e = 10000 -> 13561 30.533 ms [2:04] e = 10000 -> 13561 13.791 ms [4:09] e = 10000 -> 13561 6.436 ms [8:18] e = 10000 -> 13561 2.996 ms [1:02] e = 100000 -> 135178 2719.600 ms [2:04] e = 100000 -> 135178 1340.050 ms [4:09] e = 100000 -> 135178 588.878 ms [8:18] e = 100000 -> 135178 290.721 ms [8:18] e = 1000000 -> 1351546 28823.330 ms
对于10 ^ 6的指数，只有64位肢体的时间，因为我没有耐心等待很多分钟才能获得完整的结果。 对于基数转换，图片类似，但64位肢体没有行，因为我的编译器没有本机128位整数类型。
# E16_RadixConversion [1:02] e = 1000 -> 1366 0.080 ms [2:04] e = 1000 -> 1366 0.026 ms [4:09] e = 1000 -> 1366 0.048 ms [1:02] e = 10000 -> 13561 4.537 ms [2:04] e = 10000 -> 13561 0.746 ms [4:09] e = 10000 -> 13561 0.243 ms [1:02] e = 100000 -> 135178 445.092 ms [2:04] e = 100000 -> 135178 68.600 ms [4:09] e = 100000 -> 135178 19.344 ms [4:09] e = 1000000 -> 1351546 1925.564 ms
有趣的是，简单地将代码编译为C ++并没有使它更快 - 也就是说，优化器找不到C＃jitter错过的任何低调的结果，除了在惩罚无符号整数方面没有注意到这一点。 。 这就是为什么我喜欢在C＃中进行原型设计的原因 - 与（未优化的）C ++相同的性能并没有任何麻烦。
这是C ++版本的内容（没有像帮助模板那样无聊的东西等等），所以你可以看到我没有作弊使C＃看起来更好：
template struct E16_RadixConversion { typedef W limb_t; typedef typename detail::E16_traits::long_t long_t; static unsigned const BITS_PER_WORD = sizeof(limb_t) * CHAR_BIT; static unsigned const RADIX_DIGITS = std::numeric_limits::digits10; static limb_t const RADIX = detail::pow10_t::RESULT; static unsigned digit_sum_for_power_of_2 (unsigned e) { std::vector digits; compute_digits_for_power_of_2(e, digits); return digit_sum(digits); } static void compute_digits_for_power_of_2 (unsigned e, std::vector &result) { assert(e > 0); unsigned total_digits = unsigned(std::ceil(std::log10(2) * e)); unsigned total_limbs = (total_digits + RADIX_DIGITS - 1) / RADIX_DIGITS; result.resize(0); result.reserve(total_limbs); std::vector bin((e + BITS_PER_WORD) / BITS_PER_WORD); bin.back() = limb_t(limb_t(1) << (e % BITS_PER_WORD)); while (!bin.empty()) { long_t rest = 0; for (std::size_t i = bin.size(); i-- > 0; ) { long_t temp = (rest << BITS_PER_WORD) | bin[i]; long_t quot = temp / RADIX; rest = temp - quot * RADIX; bin[i] = limb_t(quot); } result.push_back(limb_t(rest)); if (bin.back() == 0) bin.pop_back(); } } };
结论
这些基准测试也表明，这个Euler任务 - 就像许多其他任务一样 - 似乎是为了在ZX81或Apple上解决的[，而不是我们现代玩具的强大一百万倍。 这里没有任何挑战，除非极限增加（指数10 ^ 5或10 ^ 6会更加充分）。
可以从GMP的算法概述中获得对实际技术状态的良好概述。 另一个优秀的算法概述是Richard Brent和Paul Zimmermann的“现代计算机算术”第1章。 它包含了编码挑战和竞争需要知道的内容，但不幸的是，深度不等于Donald Knuth在“计算机编程艺术”中的处理方式。
基数转换解决方案为一个代码挑战工具程序添加了一种有用的技术，因为给定代码可以简单地扩展以转换任何旧的大整数而不仅仅是位模式1 << exponent 。 重复的平方解决方案可以同样有用，因为将示例代码更改为2以外的其他内容也是微不足道的。
直接以10的幂进行计算的方法对于需要十进制结果的挑战非常有用，因为性能与本机计算处于同一个范围，但不需要单独的转换步骤（可能需要类似的时间量）实际计算）。