有沒有一種演算法可以快速找到具有大整數的多項式的值，而無需回圈？-有解無憂

例如，如果我想找到

1085912312763120759250776993188102125849391224162 = a^9 b^9 c^9 d 代碼需要帶

一個=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

uj5u.com熱心網友回復：

[更新]

下面的代碼試圖解決像 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

對于[1...N] 范圍內的每個，pow9 a[N*N]用 , 填充的表單陣列。x, y, x^9 y^9x,y

對陣列進行排序z。

到目前為止的成本O(N*N*log(N)。

對于索引為 [0...N*N/2] 的陣列元素，對另一個陣列元素進行二進制搜索，使得總和為 1085912312763120759250776993188102125849391224162

最接近的總和就是答案。

時間：O(N*N*log(N))

空間：O(N*N)

很容易從 FP 數學開始，然后用工匠擴展整數數學得到更好的答案。

嘗試使用較小N的總目標來解決實施問題。

uj5u.com熱心網友回復：

萬一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;

為了進一步提高速度，您可以通過平方使用 power 對 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的 s 而不是你的 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
    }
//-------------------------------------------------------------------------

The function bits() just returns number of occupied bits (similar to log2 but much faster). Here final results:

x = 1085912312763120759250776993188102125849391224162
    1085912312763120759250776993188102125849391224162 (reference)
a = 217423
b = 78525
c = 3456
d = 215478

It took 1689.651 ms ... As you can see this is much faster than yours however I am not sure with the number of search iterations while fine tuning ais OK or it should be scaled by a/b or even full range down to (a b)/2 which will be much slower than this...

One last thing I did not bound a,b,c to 999999 so if you want it you just add if (a>999999) a=999999; statement after any a=1<<((d.bits() 8)/9)...

[Edit1] adding binary search

Ok now all the full searches for 9th root (except of the fine tunnig of a) can be done with binary search which will improve speed a lot more while ignoring bigint multiplication complexity leads to O(n.log(n)) against your O(n^3)... Here updated code (will full iteration of a while fitting so its safe):

//---------------------------------------------------------------------------
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
    }
//-------------------------------------------------------------------------

function m.isnonzero() is the same as m!=0 just faster... The results are the same as above code but the time duration is only 821 ms for full iteration of a which would be several thousands seconds with previous code.

I think except using some polynomial discrete math trick I do not know of there is only one more thing to improve and that is to compute consequent pow9 without multiplication which will boost the speed a lot (as bigint multiplication is slowest operation by far) like I did in here:

How to get a square root for 32 bit input in one clock cycle only?

but I am too lazy to derive it...

轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/450118.html

標籤：VB.net 算法表现大整数代码结构

上一篇：將C#轉換為VB.NET'ServerCertificateValidationCallback'不是'HttpWebRequest'的事件

下一篇：按相似代碼/類別對產品進行匯總和分組