mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2016-10-05, 16:59   #1
bhelmes
 
bhelmes's Avatar
 
Mar 2016

52×11 Posts
Default 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
bhelmes is online now   Reply With Quote
Old 2016-10-05, 17:30   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20B116 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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
science_man_88 is offline   Reply With Quote
Old 2016-10-05, 20:13   #3
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

23·3·13·19 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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 View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2016-10-06, 10:45   #4
bhelmes
 
bhelmes's Avatar
 
Mar 2016

11316 Posts
Default

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
bhelmes is online now   Reply With Quote
Old 2016-10-06, 13:33   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

592810 Posts
Default

Glad I could help!
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Help with discrete logarithm pinnn Information & Answers 32 2017-11-08 00:08
Discrete logarithm software Unregistered Information & Answers 39 2012-04-27 20:08
The base of the logarithm in AKS algorithms Sairam Math 34 2011-06-12 02:24
Multiplication Tendency clowns789 Miscellaneous Math 5 2005-03-11 00:23
Montgomery Multiplication 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.