mersenneforum.org > Math multiplication and logarithm
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2016-10-05, 16:59 #1 bhelmes     Mar 2016 32·41 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

20C016 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

135338 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 17116 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 175B16 Posts Glad I could help!

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post pinnn Information & Answers 43 2021-03-18 15:40 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:24.

Wed Dec 1 21:24:30 UTC 2021 up 131 days, 15:53, 1 user, load averages: 1.55, 1.50, 1.45

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.