mersenneforum.org > Math multiplication and logarithm
 Register FAQ Search Today's Posts Mark Forums Read

 2016-10-05, 16:59 #1 bhelmes     Mar 2016 52×11 Posts multiplication and logarithm 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
2016-10-05, 17:30   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

20B116 Posts

Quote:
 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

2016-10-05, 20:13   #3
CRGreathouse

Aug 2006

23·3·13·19 Posts

Quote:
 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.

Quote:
 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.

 2016-10-06, 10:45 #4 bhelmes     Mar 2016 11316 Posts 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
 2016-10-06, 13:33 #5 CRGreathouse     Aug 2006 592810 Posts Glad I could help!

 Similar Threads Thread Thread Starter Forum Replies Last Post pinnn Information & Answers 32 2017-11-08 00:08 Unregistered Information & Answers 39 2012-04-27 20:08 Sairam Math 34 2011-06-12 02:24 clowns789 Miscellaneous Math 5 2005-03-11 00:23 dave_dm Math 2 2004-12-24 11:00

All times are UTC. The time now is 21:03.

Thu Oct 22 21:03:33 UTC 2020 up 42 days, 18:14, 0 users, load averages: 1.88, 1.92, 1.88