multiplication and logarithm

[bhelmes]

A peaceful day for all,

if i want to multiply 100 arising number of f(n)=2*n²-1 from n=1001 up to n=1100 and want to have the result modulo f.

Does it make sense to use the binary logarithm of f(n) of all terms, adding the results, do a inverse binary log of the result and make then the calculation modulo f ?

By the way the use of the logarithm of the arising numbers can it speed up by only regarding the significant different digits ?

Would be nice to get some mathematical information

Greetings from the primes
Bernhard

[science_man_88]

Originally Posted by bhelmes

A peaceful day for all,

if i want to multiply 100 arising number of f(n)=2*n²-1 from n=1001 up to n=1100 and want to have the result modulo f.

Does it make sense to use the binary logarithm of f(n) of all terms, adding the results, do a inverse binary log of the result and make then the calculation modulo f ?

By the way the use of the logarithm of the arising numbers can it speed up by only regarding the significant different digits ?

Would be nice to get some mathematical information

Greetings from the primes
Bernhard

the best method ( not necessarily within those 2) would likely depend on the properties of f if f<1001 then each n term gets reduced if it's not then it's only the terms greater than f that benefit. also if f(n) =2n^2-1 then f(n+1) = 2n^2+4n+1 aka 2(n+1)^2-1 or more generally 2(n+a)^2-1 = 2(n^2+2an+a^2)-1 = (2n^2-1) + 4an+2a^2-1 = f(n) + f(a)+4an so you can use f(n) to figure out most of it. and then mostly values of f(a) for a<101

[CRGreathouse]

Originally Posted by bhelmes

if i want to multiply 100 arising number of f(n)=2*n²-1 from n=1001 up to n=1100 and want to have the result modulo f.

Does it make sense to use the binary logarithm of f(n) of all terms, adding the results, do a inverse binary log of the result and make then the calculation modulo f ?

It seems like this would take a lot longer than just computing f(n) for each of those numbers. A better method would be to compute a polynomial for f(n)*f(n+1) or f(n)*f(n+1)*f(n+2)*f(n+3)*f(n+4) or the like, reduce coefficients mod f, and then compute these with the desired method (say, Horner's rule). Using these in a product tree yields a fairly efficient method.

There are other tricks out there like fast multipoint evaluation which are related.

Originally Posted by bhelmes

By the way the use of the logarithm of the arising numbers can it speed up by only regarding the significant different digits ?

If you need an exact answer you'll need to keep precision essentially the same, so I think the answer is "no". If you can use approximations then there are definitely better methods, depending on your needs. Doing everything like the exact case but keeping fewer digits is simplest but you can probably do a lot better.

[bhelmes]

Thanks for your nice answer.
I really appreciate to get some mathematical support from your side.

I state that you often give some really good answers, even if the question might be a little bit strange.

Thanks and best greetings from the primes
Bernhard

[CRGreathouse]

Glad I could help!