mersenneforum.org Possible better multiplication algorithm
 Register FAQ Search Today's Posts Mark Forums Read

 2015-11-02, 07:27 #1 Triber   Nov 2015 2 Posts Possible better multiplication algorithm Good day I have developed a way to accurately multiply very large integers. (millions of digits) in a reasonable fast time. It is certainly easier to explain than the Katsabura or other algorithms with iterative logarithmic functions :) I would like to verify the efficiency of the algorithm. Possible to give an indication of 2 very large numbers, with a time period, which, If I could calculate within this time, is a fair guarantee of something innovative? ( I make use of a Intel i7 process on a fairly standard laptop, 3 years old) (e.g. if the first number is a million digits of the pattern 1029384756 and the second number is a million digits of the pattern 981276345 a process to give the answer in x minutes will be innovative) Kind regards, Chris
2015-11-02, 08:36   #2
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

100110111101012 Posts

Quote:
 Originally Posted by Triber (e.g. if the first number is a million digits of the pattern 1029384756 and the second number is a million digits of the pattern 981276345 a process to give the answer in x minutes will be innovative)
Take two numbers of 75 million bits (about 22.5 million digits) and multiply them together. A time below 30 milliseconds (according to your CPU type and frequency, number of cores used, it is done with GPU help or not, etc, this can be anything between a quarter of this time, and ten times of this time) will be useful.

Remark that I didn't say "innovative", we have no idea about that, but the actual FFT algorithms can reach that time (of 30 milliseconds), using more cores of a not-so-old intel processor. If you talk about "minutes", your algorithm is not useful, even if innovative. I also made "improvements"/"variations" of karatsuba and toom-cook which could do that in "seconds". They are not useful here.

Last fiddled with by LaurV on 2015-11-02 at 09:35

2015-11-02, 09:33   #3
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

112·13 Posts

Quote:
 Originally Posted by Triber (e.g. if the first number is a million digits of the pattern 1029384756 and the second number is a million digits of the pattern 981276345 a process to give the answer in x minutes will be innovative) Kind regards, Chris
Not a very good test, Chris. I can multiply your numbers in linear time, (much) faster than FFT.

2015-11-02, 16:45   #4
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

1D2416 Posts

Quote:
 Originally Posted by Triber Good day I have developed a way to accurately multiply very large integers. (millions of digits) in a reasonable fast time. It is certainly easier to explain than the Katsabura or other algorithms with iterative logarithmic functions :)
Please tell us the time-complexity of your algorithm. As a function of n how long does it
take to multiply two n-bit numbers?

Quote:
 I would like to verify the efficiency of the algorithm. Possible to give an indication of 2 very large numbers, with a time period, which, If I could calculate within this time, is a fair guarantee of something innovative? ( I make use of a Intel i7 process on a fairly standard laptop, 3 years old)
See above. Your proposed method is not a very good measure of the effectiveness of your method.
Telling us its time complexity would be.

 2015-11-03, 07:29 #5 Triber   Nov 2015 102 Posts Thank you for the comments; regarding the number to test - I am comfortable to generate two large random numbers; this should average out of the extra time required for carry-overs from different algorithms. I am not a mathematician nor a computer scientists (although I have completed amongst others BSc computer science), the software I used to initially create my method in Microsoft SQL Server and Excel; (I know very well this is perhaps the most inappropriate software for a "production" version of an algorithm) I installed Visual studio yesterday (I have never programmed in C#) and I am making good progress to convert my algorithm. In due course I might check out other software platforms but will probably leave that to programming experts. I think the time complexity is close to N; but I do not know how to accurately calculate the time complexity with my algorithm. for example, is the time complexity identical to add two single-digit numbers exactly identical to adding two two-digit numbers? From an article I read estimation of current best standard is about 10*N*log(N); for a 22.5m digit number this is about 5.4*10^9 My estimation (probably incorrect!) for my algorithm for two 22.5m digit numbers is 2.2*10^9 Next step: I will finish the algorithm in c#, then test with two 22.5m digit random numbers, and post results. Will appreciate a reference to accurately calculate the time complexity for an algorithm.
2015-11-03, 10:38   #6
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22×5×373 Posts

Quote:
 Originally Posted by Triber Thank you for the comments; regarding the number to test - I am comfortable to generate two large random numbers; this should average out of the extra time required for carry-overs from different algorithms. I am not a mathematician nor a computer scientists (although I have completed amongst others BSc computer science), the software I used to initially create my method in Microsoft SQL Server and Excel; (I know very well this is perhaps the most inappropriate software for a "production" version of an algorithm) I installed Visual studio yesterday (I have never programmed in C#) and I am making good progress to convert my algorithm. In due course I might check out other software platforms but will probably leave that to programming experts. I think the time complexity is close to N; but I do not know how to accurately calculate the time complexity with my algorithm. for example, is the time complexity identical to add two single-digit numbers exactly identical to adding two two-digit numbers? From an article I read estimation of current best standard is about 10*N*log(N); for a 22.5m digit number this is about 5.4*10^9 My estimation (probably incorrect!) for my algorithm for two 22.5m digit numbers is 2.2*10^9 Next step: I will finish the algorithm in c#, then test with two 22.5m digit random numbers, and post results. Will appreciate a reference to accurately calculate the time complexity for an algorithm.
Show the method.

2015-11-04, 07:07   #7
Dubslow

"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·29·83 Posts

Quote:
 Originally Posted by Triber I think the time complexity is close to N; but I do not know how to accurately calculate the time complexity with my algorithm. for example, is the time complexity identical to add two single-digit numbers exactly identical to adding two two-digit numbers? From an article I read estimation of current best standard is about 10*N*log(N); for a 22.5m digit number this is about 5.4*10^9 My estimation (probably incorrect!) for my algorithm for two 22.5m digit numbers is 2.2*10^9 Next step: I will finish the algorithm in c#, then test with two 22.5m digit random numbers, and post results. Will appreciate a reference to accurately calculate the time complexity for an algorithm.
You show a certain minimal capacity for logic, hence the so far mostly encouraging replies...

However, if I may, if you have completed a BSc in computer science, you should know like the back of your hand what exactly we mean by "time complexity". It should be first or mayyybbbeee second year material for any CS student. In particular, this following quote:
Quote:
 Originally Posted by Triber is the time complexity identical to add two single-digit numbers exactly identical to adding two two-digit numbers?
shows a serious lack of fundamental understanding (which frankly makes me quite skeptical of your claim to have a BSc in CS).

In any case, "should be"s aside, this and this are the relevant Wikipedia articles (there are many other related articles of great relevance as well).

Of course there is a difference between time complexity of an algorithm, and "usefulness" of an algorithm. The best known practical algorithm today is (still) the Schönhage–Strassen algorithm, which has complexity O(n log(n) log(log(n))) (that is, greater than linear but less than quadratic complexity). The best-known complexity for multiplication is Fürer's algorithm, though as I said in practical terms, it is not useful.

And even assuming that your algorithm is "useful", there is almost certainly no way you'll be able to produce any sort of code that can be compared to state of the art implementations of the SS algorithm. As LaurV mentions, Prime95, the software for which this forum was founded, it can multiply two 75 million bit numbers (modulo a 75 million bit Mersenne number) in roughly 30-50 milliseconds on the hardware you specify.

Hopefully this shines some light on why we aren't giving you any "2 minutes will be a record" estimate (because there is no such estimate) and why we are asking you to do nothing but post your algorithm in full; we would love to help you perform a complexity analysis. Attempting to program your algorithm and post wall-clock comparisons would be a very poor way to proceed, in our opinion. (Not that we can stop you of course, and we certainly won't reject any such information, but it's likely not a good use of your time, except perhaps as a learning experience. Everyone needs more of those!)

Last fiddled with by Dubslow on 2015-11-04 at 07:12

2015-11-04, 17:25   #8
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

746010 Posts

Quote:
 Originally Posted by Dubslow You show a certain minimal capacity for logic, hence the so far mostly encouraging replies... However, if I may, if you have completed a BSc in computer science, you should know like the back of your hand what exactly we mean by "time complexity". It should be first or mayyybbbeee second year material for any CS student. In particular, this following quote: shows a serious lack of fundamental understanding (which frankly makes me quite skeptical of your claim to have a BSc in CS). In any case, "should be"s aside, this and this are the relevant Wikipedia articles (there are many other related articles of great relevance as well). Of course there is a difference between time complexity of an algorithm, and "usefulness" of an algorithm. The best known practical algorithm today is (still) the Schönhage–Strassen algorithm, which has complexity O(n log(n) log(log(n))) (that is, greater than linear but less than quadratic complexity). The best-known complexity for multiplication is Fürer's algorithm, though as I said in practical terms, it is not useful. And even assuming that your algorithm is "useful", there is almost certainly no way you'll be able to produce any sort of code that can be compared to state of the art implementations of the SS algorithm. As LaurV mentions, Prime95, the software for which this forum was founded, it can multiply two 75 million bit numbers (modulo a 75 million bit Mersenne number) in roughly 30-50 milliseconds on the hardware you specify. Hopefully this shines some light on why we aren't giving you any "2 minutes will be a record" estimate (because there is no such estimate) and why we are asking you to do nothing but post your algorithm in full; we would love to help you perform a complexity analysis. Attempting to program your algorithm and post wall-clock comparisons would be a very poor way to proceed, in our opinion. (Not that we can stop you of course, and we certainly won't reject any such information, but it's likely not a good use of your time, except perhaps as a learning experience. Everyone needs more of those!)

2015-11-05, 04:48   #9
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

9,973 Posts

Quote:
 Originally Posted by Dubslow You show
Very Dubslow!

2015-11-05, 17:36   #10
chalsall
If I May

"Chris Halsall"
Sep 2002

2×3×1,759 Posts

Quote:
 Originally Posted by Dubslow (Not that we can stop you of course, and we certainly won't reject any such information, but it's likely not a good use of your time, except perhaps as a learning experience. Everyone needs more of those!)
If I may blow some sunshine?

This is exactly what we want to see here on MersenneForum. And what all teachers want to see in others!

Only a couple of years ago you were a student here.

Now you are a teacher!

Take pride in that. Sincerely.

Last fiddled with by chalsall on 2015-11-05 at 17:37 Reason: s/where/were/

2015-11-05, 18:17   #11
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22·5·373 Posts

Quote:
 Originally Posted by chalsall If I may blow some sunshine? This is exactly what we want to see here on MersenneForum. And what all teachers want to see in others! Only a couple of years ago you were a student here. Now you are a teacher! Take pride in that. Sincerely.
Of course if I had written what Dubslow did I would be lambasted until next year.........

 Similar Threads Thread Thread Starter Forum Replies Last Post MattcAnderson Homework Help 5 2016-11-01 08:16 MattcAnderson Puzzles 8 2014-12-05 15:09 vector Miscellaneous Math 10 2007-12-20 18:16 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 13:02.

Thu Jul 7 13:02:37 UTC 2022 up 7:49, 0 users, load averages: 1.98, 1.66, 1.61