[ View Thread ] [ Post Response ] [ Return to Index ] [ Read Prev Msg ] [ Read Next Msg ]

BGonline.org Forums

Exact solution

Posted By: Timothy Chow
Date: Tuesday, 24 August 2010, at 10:08 p.m.

In Response To: Exact solution (Chuck Bower)

I'm not sure why you're trying to find clever shortcuts for a slow method.

The method using the polynomial f(x) is easy to program even if you don't have Mathematica as long as your integer variables are large enough to store the numbers in question. You don't need to keep a symbolic "x" around. Just represent a polynomial as an array of coefficients. Multiplying two polynomials f and g is just a nested do-loop:

for n from 0 to 43 do
h[n] = 0
for d from 0 to n do
h[n] = h[n] + f[d]*g[n-d]
end do
end do

To compute f(x)9, you can square f(x) to get f(x)2, square again to get f(x)4, and square a third time to get f(x)8, and finally multiply f(x) by f(x)8. That's four polynomial multiplications. At each stage you need only keep the coefficients up to x43 and you can throw away the higher coefficients because they will never contribute to the final answer you want. All this should take only a few thousand arithmetic operations.

Messages In This Thread

 

Post Response
Your Name:
Your E-Mail Address:
Subject:
Message:

If necessary, enter your password below:

Password:
 

 

[ View Thread ] [ Post Response ] [ Return to Index ] [ Read Prev Msg ] [ Read Next Msg ]

BGonline.org Forums is maintained by Stick with WebBBS 5.12.