# [SOLVED] Is there an algorithm, to find values ​of a polynomial with big integers, quickly without loops?

## Issue

For example, if I want to find

1085912312763120759250776993188102125849391224162 = a^9+b^9+c^9+d
the code needs to brings

a=3456

b=78525

c=217423

d=215478

I do not need specific values, only that they comply with the fact that a, b and c have 6 digits at most and d is as small as possible.

Is there a quick way to find it?

I have tried with nested loops but it is extremely slow and the code gets stuck.

Any help in VB or other code would be appreciated. I think the structure is more important than the language in this case

``````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
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
``````

## Solution

In case `a,b,c,d` might be zero I got an Idea for fast and simple solution:

First something better than brute force search of `a^9 + d = x` so that `a` is maximal (that ensures minimal `d`)…

1. let `d = 1085912312763120759250776993188102125849391224162`

2. find max value `a` such that `a^9 <= d`

this is simple as we know 9th power will multiply the bitwidth of operand 9 times so the max value can be at most `a <= 2^(log2(d)/9)` Now just search all numbers from this number down to zero (decrementing) until its 9th power is less or equal to `x`. This value will be our `a`.

Its still brute force search however from much better starting point so much less iterations are required.

3. We also need to update `d` so let

``````d = d - a^9
``````

Now just find `b,c` in the same way (using smaller and smaller remainder `d`)… these searches are not nested so they are fast …

``````b^9 <= d; d-=b^9;
c^9 <= d; c-=b^9;
``````

To improve speed even more you can hardcode the 9th power using power by squaring …

This will be our initial solution (on mine setup it took ~200ms with 32*8 bits uints) with these results:

``````x = 1085912312763120759250776993188102125849391224162
1085912312763120759250776993188102125849391224162 (reference)
a = 217425
b = 65957
c = 22886
d = 39113777348346762582909125401671564
``````

Now we want to minimize `d` so simply decrement `a` and search `b` upwards until still `a^9 + b^9 <= d` is lower. Then search `c` as before and remember better solution. The a should be search downwards to meet `b` in the middle but as both `a` and `b`have the same powers only few iterations might suffice (I used 50) from the first solution (but I have no proof of this its just my feeling). But still even if full range is used this has less complexity than yours as I have just 2 nested `for`s instead of yours 3 and they all are with lower ranges…

Here small working C++ example (sorry do not code in BASIC for decades):

``````//---------------------------------------------------------------------------
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 `a`is 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)`