mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2015-11-02, 07:27   #1
Triber
 
Nov 2015

216 Posts
Question 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
Triber is offline   Reply With Quote
Old 2015-11-02, 08:36   #2
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

9,787 Posts
Default

Quote:
Originally Posted by Triber View Post
(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
LaurV is offline   Reply With Quote
Old 2015-11-02, 09:33   #3
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2×32×83 Posts
Default

Quote:
Originally Posted by Triber View Post
(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.
R. Gerbicz is offline   Reply With Quote
Old 2015-11-02, 16:45   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Default

Quote:
Originally Posted by Triber View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2015-11-03, 07:29   #5
Triber
 
Nov 2015

216 Posts
Default

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.
Triber is offline   Reply With Quote
Old 2015-11-03, 10:38   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Default

Quote:
Originally Posted by Triber View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2015-11-04, 07:07   #7
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·29·83 Posts
Default

Quote:
Originally Posted by Triber View Post
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 View Post
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
Dubslow is offline   Reply With Quote
Old 2015-11-04, 17:25   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164448 Posts
Default

Quote:
Originally Posted by Dubslow View Post
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!)

R.D. Silverman is offline   Reply With Quote
Old 2015-11-05, 04:48   #9
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

100110001110112 Posts
Default

Quote:
Originally Posted by Dubslow View Post
You show <snip>
Very Dubslow!
LaurV is offline   Reply With Quote
Old 2015-11-05, 17:36   #10
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

23×433 Posts
Default

Quote:
Originally Posted by Dubslow View Post
(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/
chalsall is offline   Reply With Quote
Old 2015-11-05, 18:17   #11
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by chalsall View Post
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.........
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A Fib expression with multiplication MattcAnderson Homework Help 5 2016-11-01 08:16
5 digit multiplication MattcAnderson Puzzles 8 2014-12-05 15:09
New Multiplication Algorithm vector Miscellaneous Math 10 2007-12-20 18:16
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 05:59.


Sat Oct 23 05:59:29 UTC 2021 up 92 days, 28 mins, 0 users, load averages: 0.77, 1.10, 1.23

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.