是否有一种算法可以在没有循环的情况下快速找到具有大整数的多项式的值？
Is there an algorithm, to find values of a polynomial with big integers, quickly without loops?
例如，如果我想查找
1085912312763120759250776993188102125849391224162 = a^9+b^9+c^9+d
代码需要带
a=3456
b=78525
c=217423
d=215478
我不需要具体的数值，只要符合a,b,c最多6位，d尽量小
有没有快速找到的方法？
感谢您能给我的任何帮助。
我试过嵌套循环，但速度非常慢，而且代码卡住了。
VB 或其他代码中的任何帮助将不胜感激。我认为在这种情况下结构比语言更重要
Imports System.Numerics
Public Class Form1
Private Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click
Dim Value As BigInteger = BigInteger.Parse("1085912312763120759250776993188102125849391224162")
Dim powResult As BigInteger
Dim dResult As BigInteger
Dim a As Integer
Dim b As Integer
Dim c As Integer
Dim d As Integer
For i = 1 To 999999
For j = 1 To 999999
For k = 1 To 999999
powResult = BigInteger.Add(BigInteger.Add(BigInteger.Pow(i, 9), BigInteger.Pow(j, 9)), BigInteger.Pow(k, 9))
dResult = BigInteger.Subtract(Value, powResult)
If Len(dResult.ToString) <= 6 Then
a = i
b = j
c = k
d = dResult
RichTextBox1.Text = a & " , " & b & " , " & c & " , " & d
Exit For
Exit For
Exit For
End If
Next
Next
Next
End Sub
End Class
更新
我把代码写在了vb。但是这段代码，a对，b对c错，结果不对。
a^9 + b^9 + c^9 + d 是一个比初始值大的数。
代码应该带来
a=217423
b=78525
c=3456
d=215478
总值还可以= 1085912312763120759250776993188102125849391224162
但代码带来
a=217423
b=78525
c=65957
d=70333722607339201875244531009974
总值大于等于=1085935936469985777155428248430866412402362281319
我需要更改什么代码才能使 c= 3456 和 d= 215478？
密码是
进口System.Numerics
Public Class 表格 1
私有函数 pow9(x As BigInteger) As BigInteger
Dim y As BigInteger
y = x * x ' x^2
y *= y ' x^4
y *= y ' x^8
y *= x ' x^9
Return是的
结束函数
Private Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click
Dim a, b, c, d, D2, n As BigInteger
Dim aa, bb, cc, dd, ae As BigInteger
D2 = BigInteger.Parse("1085912312763120759250776993188102125849391224162")
'first solution so a is maximal
d = D2
'a = BigIntegerSqrt(D2)
'RichTextBox1.Text = a.ToString
For a = 1 << ((Convert.ToInt32(Math.Ceiling(BigInteger.Log(d, 2))) + 8) / 9) To a > 0 Step -1
If (pow9(a) <= d) Then
d -= pow9(a)
Exit For
End If
Next
For b = 1 << ((Convert.ToInt32(Math.Ceiling(BigInteger.Log(d, 2))) + 8) / 9) To b > 0 Step -1
If (pow9(b) <= d) Then
d -= pow9(b)
Exit For
End If
Next
For c = 1 << ((Convert.ToInt32(Math.Ceiling(BigInteger.Log(d, 2))) + 8) / 9) To c > 0 Step -1
If (pow9(c) <= d) Then
d -= pow9(c)
Exit For
End If
Next
' minimize d
aa = a
bb = b
cc = c
dd = d
If (aa < 10) Then
ae = 0
Else
ae = aa - 10
End If
For a = aa - 1 To a > ae Step -1 'a goes down few iterations
d = D2 - pow9(a)
For n = 1 << ((Convert.ToInt32(Math.Ceiling(BigInteger.Log(d, 2))) + 8) / 9) To b < n 'b goes up
If (pow9(b) >= d) Then
b = b - 1
d -= pow9(b)
Exit For
End If
Next
For c = 1 << ((Convert.ToInt32(Math.Ceiling(BigInteger.Log(d, 2))) + 8) / 9) To c > 0 Step -1 'c must be search fully
If pow9(c) <= d Then
d -= pow9(c)
Exit For
End If
Next
If d < dd Then 'remember better solution
aa = a
bb = b
cc = c
dd = d
End If
If a < ae Then
Exit For
End If
Next
a = aa
b = bb
c = cc
d = dd
' a,b,c,d is the result
RichTextBox1.Text = D2.ToString
Dim Sum As BigInteger
Dim a9 As BigInteger
Dim b9 As BigInteger
Dim c9 As BigInteger
a9 = BigInteger.Pow(a, 9)
b9 = BigInteger.Pow(b, 9)
c9 = BigInteger.Pow(c, 9)
Sum = BigInteger.Add(BigInteger.Add(BigInteger.Add(a9, b9), c9), d)
RichTextBox2.Text = Sum.ToString
Dim Subst As BigInteger
Subst = BigInteger.Subtract(Sum, D2)
RichTextBox3.Text = Subst.ToString
End Sub
结束Class
[更新]
下面的代码试图解决像 OP 一样的问题，但我读错了。
以下是 1085912312763120759250776993188102125849391224162 = a^9+b^9+c^9+d^9+e 的最小化 e.
刚刚对 OP 的有趣难题过于兴奋，阅读速度过快。
我稍后再回顾这个。
OP 的方法是 O(N*N*N*N) - 慢
下面是 O(N*N*log(N)) 一个。
算法
令 N = 1,000,000。 （看起来 250,000 足以满足 OP 的总和 1.0859e48。）
定义 160 多个宽整数数学例程。
定义类型：pow9
int x,y,
int160least_t z
表格数组 pow9 a[N*N] 填充了 x, y, x^9 + y^9，对于 [1...N] 范围内的每个 x,y。
在 z 上对数组进行排序。
到目前为止的费用 O(N*N*log(N)。
对于索引为 [0...N*N/2] 的数组元素，对另一个数组元素进行二进制搜索，使得总和为 1085912312763120759250776993188102125849391224162
总和最接近的就是答案。
时间：O(N*N*log(N))
Space: O(N*N)
从 FP 数学开始很容易，然后通过 crafter 扩展整数数学得到更好的答案。
尝试使用更小的 N 和总和目标来解决实施问题。
如果 a,b,c,d 可能为零，我想到了一个快速简单的解决方案：
首先是比暴力搜索 a^9 + d = x 更好的东西，这样 a 是最大的（确保最小 d）...
让d = 1085912312763120759250776993188102125849391224162
找到最大值 a 使得 a^9 <= d
这很简单，因为我们知道 9 次方会将操作数的位宽乘以 9 倍，因此最大值最多可以是 a <= 2^(log2(d)/9)现在只需搜索从该数字开始的所有数字直到零（递减）直到它9 次方小于或等于 x。这个值将是我们的 a.
它仍然是蛮力搜索，但是从更好的起点开始，因此需要更少的迭代。
我们还需要更新d所以让
d = d - a^9
现在只需以相同的方式查找 b,c（使用越来越小的余数 d）...这些搜索没有嵌套，因此速度很快...
b^9 <= d; d-=b^9;
c^9 <= d; c-=b^9;
要进一步提高速度，您可以使用幂的平方对 9 次方进行硬编码...
这将是我们的初始解决方案（在我的设置中，使用 32*8 位 uint 花费了约 200 毫秒），结果如下：
x = 1085912312763120759250776993188102125849391224162
1085912312763120759250776993188102125849391224162 (reference)
a = 217425
b = 65957
c = 22886
d = 39113777348346762582909125401671564
现在我们要最小化 d，因此只需递减 a 并向上搜索 b，直到 a^9 + b^9 <= d 仍然较低。然后像以前一样搜索 c 并记住更好的解决方案。 a 应该向下搜索以在中间遇到 b 但由于 a 和 b 具有相同的权力，只有少数迭代可能就足够了（我使用了 50）来自第一个解决方案（但我没有证据证明这只是我的感觉)。但是仍然即使使用了全范围，它的复杂性也比你的要低，因为我只有 2 个嵌套 for 而不是你的 3 个，而且它们都具有较低的范围...
这里是小的工作 C++ 示例（抱歉几十年来没有用 BASIC 编写代码）：
//---------------------------------------------------------------------------
typedef uint<8> bigint;
//---------------------------------------------------------------------------
bigint pow9(bigint &x)
{
bigint y;
y=x*x; // x^2
y*=y; // x^4
y*=y; // x^8
y*=x; // x^9
return y;
}
//---------------------------------------------------------------------------
void compute()
{
bigint a,b,c,d,D,n;
bigint aa,bb,cc,dd,ae;
D="1085912312763120759250776993188102125849391224162";
// first solution so a is maximal
d=D;
for (a=1<<((d.bits()+8)/9);a>0;a--) if (pow9(a)<=d) break; d-=pow9(a);
for (b=1<<((d.bits()+8)/9);b>0;b--) if (pow9(b)<=d) break; d-=pow9(b);
for (c=1<<((d.bits()+8)/9);c>0;c--) if (pow9(c)<=d) break; d-=pow9(c);
// minimize d
aa=a; bb=b; cc=c; dd=d;
if (aa<50) ae=0; else ae=aa-50;
for (a=aa-1;a>ae;a--) // a goes down few iterations
{
d=D-pow9(a);
for (n=1<<((d.bits()+8)/9),b++;b<n;b++) if (pow9(b)>=d) break; b--; d-=pow9(b); // b goes up
for (c=1<<((d.bits()+8)/9);c>0;c--) if (pow9(c)<=d) break; d-=pow9(c); // c must be search fully
if (d<dd) // remember better solution
{
aa=a; bb=b; cc=c; dd=d;
}
}
a=aa; b=bb; c=cc; d=dd; // a,b,c,d is the result
}
//-------------------------------------------------------------------------
函数 bits() 只是 returns 占用的位数（类似于 log2 但速度更快）。这里是最终结果：
x = 1085912312763120759250776993188102125849391224162
1085912312763120759250776993188102125849391224162 (reference)
a = 217423
b = 78525
c = 3456
d = 215478
它花了 1689.651 毫秒...正如你所看到的，这比你的快得多但是我不确定搜索迭代的次数，而微调 a 是可以的，或者它应该按 a/b 甚至全范围下降到 (a+b)/2 这将比这慢得多...
最后一件事我没有将 a、b、c 绑定到 999999 所以如果你想要它你只需在任何 a=1<<((d.bits()+8)/9)...[=57 之后添加 if (a>999999) a=999999; 语句=]
[Edit1] 添加二进制搜索
现在所有对第 9 根的完整搜索（a 的微调除外）都可以使用二进制搜索来完成，这将大大提高速度，同时忽略 bigint 乘法复杂性导致 O(n.log(n)) 反对你的 O(n^3)... 这里更新了代码（将 a 的完整迭代，同时适合它的安全）：
//---------------------------------------------------------------------------
typedef uint<8> bigint;
//---------------------------------------------------------------------------
bigint pow9(bigint &x)
{
bigint y;
y=x*x; // x^2
y*=y; // x^4
y*=y; // x^8
y*=x; // x^9
return y;
}
//---------------------------------------------------------------------------
bigint binsearch_max_pow9(bigint &d) // return biggest x, where x^9 <= d, and lower d by x^9
{ // x = floor(d^(1/9)) , d = remainder
bigint m,x;
for (m=bigint(1)<<((d.bits()+8)/9),x=0;m.isnonzero();m>>=1)
{ x|=m; if (pow9(x)>d) x^=m; }
d-=pow9(x);
return x;
}
//---------------------------------------------------------------------------
void compute()
{
bigint a,b,c,d,D,n;
bigint aa,bb,cc,dd;
D="1085912312763120759250776993188102125849391224162";
// first solution so a is maximal
d=D;
a=binsearch_max_pow9(d);
b=binsearch_max_pow9(d);
c=binsearch_max_pow9(d);
// minimize d
aa=a; bb=b; cc=c; dd=d;
for (a=aa-1;a>=b;a--) // a goes down few iterations
{
d=D-pow9(a);
for (n=1<<((d.bits()+8)/9),b++;b<n;b++) if (pow9(b)>=d) break; b--; d-=pow9(b); // b goes up
c=binsearch_max_pow9(d);
if (d<dd) // remember better solution
{
aa=a; bb=b; cc=c; dd=d;
}
}
a=aa; b=bb; c=cc; d=dd; // a,b,c,d is the result
}
//-------------------------------------------------------------------------
函数 m.isnonzero() 与 m!=0 相同，只是速度更快...结果与上面的代码相同，但持续时间仅为 821 ms [= 的完整迭代18=] 这将是几千秒与以前的代码。
我认为除了使用一些我不知道的多项式离散数学技巧之外，只有一件事需要改进，那就是计算结果 pow9 而无需乘法，这将大大提高速度（如 bigint multiplication 是迄今为止最慢的操作）就像我在这里所做的那样：
- How to get a square root for 32 bit input in one clock cycle only?
不过懒得推导了...
例如，如果我想查找
1085912312763120759250776993188102125849391224162 = a^9+b^9+c^9+d 代码需要带
a=3456
b=78525
c=217423
d=215478
我不需要具体的数值，只要符合a,b,c最多6位，d尽量小
有没有快速找到的方法？
感谢您能给我的任何帮助。
我试过嵌套循环，但速度非常慢，而且代码卡住了。
VB 或其他代码中的任何帮助将不胜感激。我认为在这种情况下结构比语言更重要
Imports System.Numerics
Public Class Form1
Private Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click
Dim Value As BigInteger = BigInteger.Parse("1085912312763120759250776993188102125849391224162")
Dim powResult As BigInteger
Dim dResult As BigInteger
Dim a As Integer
Dim b As Integer
Dim c As Integer
Dim d As Integer
For i = 1 To 999999
For j = 1 To 999999
For k = 1 To 999999
powResult = BigInteger.Add(BigInteger.Add(BigInteger.Pow(i, 9), BigInteger.Pow(j, 9)), BigInteger.Pow(k, 9))
dResult = BigInteger.Subtract(Value, powResult)
If Len(dResult.ToString) <= 6 Then
a = i
b = j
c = k
d = dResult
RichTextBox1.Text = a & " , " & b & " , " & c & " , " & d
Exit For
Exit For
Exit For
End If
Next
Next
Next
End Sub
End Class
更新
我把代码写在了vb。但是这段代码，a对，b对c错，结果不对。
a^9 + b^9 + c^9 + d 是一个比初始值大的数。
代码应该带来
a=217423
b=78525
c=3456
d=215478
总值还可以= 1085912312763120759250776993188102125849391224162
但代码带来
a=217423
b=78525
c=65957
d=70333722607339201875244531009974
总值大于等于=1085935936469985777155428248430866412402362281319
我需要更改什么代码才能使 c= 3456 和 d= 215478？
密码是
进口System.Numerics Public Class 表格 1 私有函数 pow9(x As BigInteger) As BigInteger Dim y As BigInteger y = x * x ' x^2 y *= y ' x^4 y *= y ' x^8 y *= x ' x^9 Return是的 结束函数
Private Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click
Dim a, b, c, d, D2, n As BigInteger
Dim aa, bb, cc, dd, ae As BigInteger
D2 = BigInteger.Parse("1085912312763120759250776993188102125849391224162")
'first solution so a is maximal
d = D2
'a = BigIntegerSqrt(D2)
'RichTextBox1.Text = a.ToString
For a = 1 << ((Convert.ToInt32(Math.Ceiling(BigInteger.Log(d, 2))) + 8) / 9) To a > 0 Step -1
If (pow9(a) <= d) Then
d -= pow9(a)
Exit For
End If
Next
For b = 1 << ((Convert.ToInt32(Math.Ceiling(BigInteger.Log(d, 2))) + 8) / 9) To b > 0 Step -1
If (pow9(b) <= d) Then
d -= pow9(b)
Exit For
End If
Next
For c = 1 << ((Convert.ToInt32(Math.Ceiling(BigInteger.Log(d, 2))) + 8) / 9) To c > 0 Step -1
If (pow9(c) <= d) Then
d -= pow9(c)
Exit For
End If
Next
' minimize d
aa = a
bb = b
cc = c
dd = d
If (aa < 10) Then
ae = 0
Else
ae = aa - 10
End If
For a = aa - 1 To a > ae Step -1 'a goes down few iterations
d = D2 - pow9(a)
For n = 1 << ((Convert.ToInt32(Math.Ceiling(BigInteger.Log(d, 2))) + 8) / 9) To b < n 'b goes up
If (pow9(b) >= d) Then
b = b - 1
d -= pow9(b)
Exit For
End If
Next
For c = 1 << ((Convert.ToInt32(Math.Ceiling(BigInteger.Log(d, 2))) + 8) / 9) To c > 0 Step -1 'c must be search fully
If pow9(c) <= d Then
d -= pow9(c)
Exit For
End If
Next
If d < dd Then 'remember better solution
aa = a
bb = b
cc = c
dd = d
End If
If a < ae Then
Exit For
End If
Next
a = aa
b = bb
c = cc
d = dd
' a,b,c,d is the result
RichTextBox1.Text = D2.ToString
Dim Sum As BigInteger
Dim a9 As BigInteger
Dim b9 As BigInteger
Dim c9 As BigInteger
a9 = BigInteger.Pow(a, 9)
b9 = BigInteger.Pow(b, 9)
c9 = BigInteger.Pow(c, 9)
Sum = BigInteger.Add(BigInteger.Add(BigInteger.Add(a9, b9), c9), d)
RichTextBox2.Text = Sum.ToString
Dim Subst As BigInteger
Subst = BigInteger.Subtract(Sum, D2)
RichTextBox3.Text = Subst.ToString
End Sub
结束Class
[更新]
下面的代码试图解决像 OP 一样的问题，但我读错了。
以下是 1085912312763120759250776993188102125849391224162 = a^9+b^9+c^9+d^9+e 的最小化 e.
刚刚对 OP 的有趣难题过于兴奋，阅读速度过快。
我稍后再回顾这个。
OP 的方法是 O(N*N*N*N) - 慢
下面是 O(N*N*log(N)) 一个。
算法
令 N = 1,000,000。 （看起来 250,000 足以满足 OP 的总和 1.0859e48。）
定义 160 多个宽整数数学例程。
定义类型：pow9
int x,y,
int160least_t z
表格数组 pow9 a[N*N] 填充了 x, y, x^9 + y^9，对于 [1...N] 范围内的每个 x,y。
在 z 上对数组进行排序。
到目前为止的费用 O(N*N*log(N)。
对于索引为 [0...N*N/2] 的数组元素，对另一个数组元素进行二进制搜索，使得总和为 1085912312763120759250776993188102125849391224162
总和最接近的就是答案。
时间：O(N*N*log(N))
Space: O(N*N)
从 FP 数学开始很容易，然后通过 crafter 扩展整数数学得到更好的答案。
尝试使用更小的 N 和总和目标来解决实施问题。
如果 a,b,c,d 可能为零，我想到了一个快速简单的解决方案：
首先是比暴力搜索 a^9 + d = x 更好的东西，这样 a 是最大的（确保最小 d）...
让
d = 1085912312763120759250776993188102125849391224162找到最大值
a使得a^9 <= d这很简单，因为我们知道 9 次方会将操作数的位宽乘以 9 倍，因此最大值最多可以是
a <= 2^(log2(d)/9)现在只需搜索从该数字开始的所有数字直到零（递减）直到它9 次方小于或等于x。这个值将是我们的a.它仍然是蛮力搜索，但是从更好的起点开始，因此需要更少的迭代。
我们还需要更新
d所以让d = d - a^9
现在只需以相同的方式查找 b,c（使用越来越小的余数 d）...这些搜索没有嵌套，因此速度很快...
b^9 <= d; d-=b^9;
c^9 <= d; c-=b^9;
要进一步提高速度，您可以使用幂的平方对 9 次方进行硬编码...
这将是我们的初始解决方案（在我的设置中，使用 32*8 位 uint 花费了约 200 毫秒），结果如下：
x = 1085912312763120759250776993188102125849391224162
1085912312763120759250776993188102125849391224162 (reference)
a = 217425
b = 65957
c = 22886
d = 39113777348346762582909125401671564
现在我们要最小化 d，因此只需递减 a 并向上搜索 b，直到 a^9 + b^9 <= d 仍然较低。然后像以前一样搜索 c 并记住更好的解决方案。 a 应该向下搜索以在中间遇到 b 但由于 a 和 b 具有相同的权力，只有少数迭代可能就足够了（我使用了 50）来自第一个解决方案（但我没有证据证明这只是我的感觉)。但是仍然即使使用了全范围，它的复杂性也比你的要低，因为我只有 2 个嵌套 for 而不是你的 3 个，而且它们都具有较低的范围...
这里是小的工作 C++ 示例（抱歉几十年来没有用 BASIC 编写代码）：
//---------------------------------------------------------------------------
typedef uint<8> bigint;
//---------------------------------------------------------------------------
bigint pow9(bigint &x)
{
bigint y;
y=x*x; // x^2
y*=y; // x^4
y*=y; // x^8
y*=x; // x^9
return y;
}
//---------------------------------------------------------------------------
void compute()
{
bigint a,b,c,d,D,n;
bigint aa,bb,cc,dd,ae;
D="1085912312763120759250776993188102125849391224162";
// first solution so a is maximal
d=D;
for (a=1<<((d.bits()+8)/9);a>0;a--) if (pow9(a)<=d) break; d-=pow9(a);
for (b=1<<((d.bits()+8)/9);b>0;b--) if (pow9(b)<=d) break; d-=pow9(b);
for (c=1<<((d.bits()+8)/9);c>0;c--) if (pow9(c)<=d) break; d-=pow9(c);
// minimize d
aa=a; bb=b; cc=c; dd=d;
if (aa<50) ae=0; else ae=aa-50;
for (a=aa-1;a>ae;a--) // a goes down few iterations
{
d=D-pow9(a);
for (n=1<<((d.bits()+8)/9),b++;b<n;b++) if (pow9(b)>=d) break; b--; d-=pow9(b); // b goes up
for (c=1<<((d.bits()+8)/9);c>0;c--) if (pow9(c)<=d) break; d-=pow9(c); // c must be search fully
if (d<dd) // remember better solution
{
aa=a; bb=b; cc=c; dd=d;
}
}
a=aa; b=bb; c=cc; d=dd; // a,b,c,d is the result
}
//-------------------------------------------------------------------------
函数 bits() 只是 returns 占用的位数（类似于 log2 但速度更快）。这里是最终结果：
x = 1085912312763120759250776993188102125849391224162
1085912312763120759250776993188102125849391224162 (reference)
a = 217423
b = 78525
c = 3456
d = 215478
它花了 1689.651 毫秒...正如你所看到的，这比你的快得多但是我不确定搜索迭代的次数，而微调 a 是可以的，或者它应该按 a/b 甚至全范围下降到 (a+b)/2 这将比这慢得多...
最后一件事我没有将 a、b、c 绑定到 999999 所以如果你想要它你只需在任何 a=1<<((d.bits()+8)/9)...[=57 之后添加 if (a>999999) a=999999; 语句=]
[Edit1] 添加二进制搜索
现在所有对第 9 根的完整搜索（a 的微调除外）都可以使用二进制搜索来完成，这将大大提高速度，同时忽略 bigint 乘法复杂性导致 O(n.log(n)) 反对你的 O(n^3)... 这里更新了代码（将 a 的完整迭代，同时适合它的安全）：
//---------------------------------------------------------------------------
typedef uint<8> bigint;
//---------------------------------------------------------------------------
bigint pow9(bigint &x)
{
bigint y;
y=x*x; // x^2
y*=y; // x^4
y*=y; // x^8
y*=x; // x^9
return y;
}
//---------------------------------------------------------------------------
bigint binsearch_max_pow9(bigint &d) // return biggest x, where x^9 <= d, and lower d by x^9
{ // x = floor(d^(1/9)) , d = remainder
bigint m,x;
for (m=bigint(1)<<((d.bits()+8)/9),x=0;m.isnonzero();m>>=1)
{ x|=m; if (pow9(x)>d) x^=m; }
d-=pow9(x);
return x;
}
//---------------------------------------------------------------------------
void compute()
{
bigint a,b,c,d,D,n;
bigint aa,bb,cc,dd;
D="1085912312763120759250776993188102125849391224162";
// first solution so a is maximal
d=D;
a=binsearch_max_pow9(d);
b=binsearch_max_pow9(d);
c=binsearch_max_pow9(d);
// minimize d
aa=a; bb=b; cc=c; dd=d;
for (a=aa-1;a>=b;a--) // a goes down few iterations
{
d=D-pow9(a);
for (n=1<<((d.bits()+8)/9),b++;b<n;b++) if (pow9(b)>=d) break; b--; d-=pow9(b); // b goes up
c=binsearch_max_pow9(d);
if (d<dd) // remember better solution
{
aa=a; bb=b; cc=c; dd=d;
}
}
a=aa; b=bb; c=cc; d=dd; // a,b,c,d is the result
}
//-------------------------------------------------------------------------
函数 m.isnonzero() 与 m!=0 相同，只是速度更快...结果与上面的代码相同，但持续时间仅为 821 ms [= 的完整迭代18=] 这将是几千秒与以前的代码。
我认为除了使用一些我不知道的多项式离散数学技巧之外，只有一件事需要改进，那就是计算结果 pow9 而无需乘法，这将大大提高速度（如 bigint multiplication 是迄今为止最慢的操作）就像我在这里所做的那样：
- How to get a square root for 32 bit input in one clock cycle only?
不过懒得推导了...