mersenneforum.org New Multiplication Algorithm
 Register FAQ Search Today's Posts Mark Forums Read

 2007-12-15, 10:18 #1 vector     Nov 2007 home 1916 Posts New Multiplication Algorithm I just coded a new multiplication algorithm which slower than trial multiplication It is in java code. Code: import java.math.BigInteger; import java.util.ArrayList; import java.util.Random; public class Main { public static BigInteger zero=BigInteger.valueOf(0); public static BigInteger one=BigInteger.valueOf(1); public static Random rnd=new Random();//randomizer public static void main(String[] args) { ArrayListprimes=new ArrayList(); ArrayListresedues=new ArrayList(); ArrayListmoduli=new ArrayList(); for(int i=2;i<100000;i++){ if(BigInteger.valueOf(i).isProbablePrime(30)){ primes.add(BigInteger.valueOf(i)); } } BigInteger number1=BigInteger.probablePrime(20,rnd); for(int i=0;i<1000;i++){ number1=number1.multiply(BigInteger.probablePrime(20,rnd)); } BigInteger number2=BigInteger.probablePrime(20,rnd); for(int i=0;i<1000;i++){ number2=number2.multiply(BigInteger.probablePrime(20,rnd)); } long start=System.nanoTime(); BigInteger temp=number1.multiply(number2); long end=System.nanoTime()-start; System.out.println("slow multiplication time: "+end+"ns"); System.out.println("slow multiplication time: "+temp); System.out.println("bitlength: "+temp.bitLength()); BigInteger compositemod=one; int totallength=number1.bitLength()+number2.bitLength()+1; start=System.nanoTime(); for(int i=0;itotallength){ i=primes.size(); } } } } BigInteger x=zero; for(int i=0;i
2007-12-15, 11:18   #2
xilman
Bamboozled!

"ð’‰ºð’ŒŒð’‡·ð’†·ð’€­"
May 2003
Down not across

278E16 Posts

Quote:
 Originally Posted by vector I just coded a new multiplication algorithm which slower than trial multiplication It is in java code.
Why?

I snipped the code because it is totally uncommented and there is no external description either.

Paul

 2007-12-15, 12:50 #3 vector     Nov 2007 home 318 Posts Ok I commented the code. Code: import java.math.BigInteger;//imports import java.util.ArrayList; import java.util.Random; public class Main { //global vars public static BigInteger zero=BigInteger.valueOf(0); public static BigInteger one=BigInteger.valueOf(1); public static Random rnd=new Random();//randomizer public static void main(String[] args) { ArrayListprimes=new ArrayList();//list of primes ArrayListresedues=new ArrayList();//list of resedues ArrayListmoduli=new ArrayList();//list of modulus primes //this generates and stores primes for(int i=2;i<100000;i++){ if(BigInteger.valueOf(i).isProbablePrime(30)){ primes.add(BigInteger.valueOf(i)); } } //this part generates 2 large random bigintegers BigInteger number1=BigInteger.probablePrime(20,rnd); for(int i=0;i<1000;i++){ number1=number1.multiply(BigInteger.probablePrime(20,rnd)); } BigInteger number2=BigInteger.probablePrime(20,rnd); for(int i=0;i<1000;i++){ number2=number2.multiply(BigInteger.probablePrime(20,rnd)); } //multiplication is made using standard java method and analyzed long start=System.nanoTime(); BigInteger temp=number1.multiply(number2); long end=System.nanoTime()-start; System.out.println("slow multiplication time: "+end+"ns"); System.out.println("slow multiplication time: "+temp); System.out.println("bitlength: "+temp.bitLength()); BigInteger compositemod=one;//initialized modulus int totallength=number1.bitLength()+number2.bitLength()+1;//calculate limit of modulus size at which to stop iterating start=System.nanoTime();//start times for(int i=0;itotallength){//check whether to end the loop i=primes.size(); } } } } BigInteger x=zero;//initialize product variable //this part multiplies/solves all of the product congruences together for(int i=0;i
 2007-12-15, 13:44 #4 rogue     "Mark" Apr 2003 Between here and the 174116 Posts Again, the question is why?
 2007-12-15, 14:12 #5 vector     Nov 2007 home 52 Posts Why what?
2007-12-15, 17:04   #6
rogue

"Mark"
Apr 2003
Between here and the

5,953 Posts

Quote:
 Originally Posted by vector Why what?
If I read your original post correctly, your code wouldn't be useful for anyone, so why would you write it? I also don't know what you mean by "trial multiplication".

 2007-12-15, 19:59 #7 vector     Nov 2007 home 52 Posts I wrote it because I thought it would result in faster multiplication than the bigInteger multiplication method. It is supposed to break the large multiplication problem into many small multiplication problems which I though would take less time to complete than the one large multiplication. There are use for this though. You can use this multiplication instead of the fft to slow down the execution of many factoring programs. Just for fun of course. On theoretical grounds this is the only multiplication algorithm I know which is both faster than exponential and slower than O(n^2) trial multiplication.
 2007-12-15, 20:52 #8 akruppa     "Nancy" Aug 2002 Alexandria 25×7×11 Posts Moved to Misc. Math. Alex
2007-12-19, 14:30   #9
alpertron

Aug 2002
Buenos Aires, Argentina

133310 Posts

Quote:
 Originally Posted by vector ... On theoretical grounds this is the only multiplication algorithm I know which is both faster than exponential and slower than O(n^2) trial multiplication.
Well, you can also compute the logarithm of the absolute value of both numbers to multiply, add them, and then find its antilogarithm. Finally adjust the sign as appropiate. This is slower than O(n^2) but not exponential.

2007-12-20, 15:03   #10
R.D. Silverman

Nov 2003

161008 Posts

Quote:
 Originally Posted by vector I wrote it because I thought it would result in faster multiplication than the bigInteger multiplication method. It is supposed to break the large multiplication problem into many small multiplication problems which I though would take less time to complete than the one large multiplication. There are use for this though. You can use this multiplication instead of the fft to slow down the execution of many factoring programs. Just for fun of course. On theoretical grounds this is the only multiplication algorithm I know which is both faster than exponential and slower than O(n^2) trial multiplication.

Clueless.

 2007-12-20, 18:16 #11 ewmayer ∂2ω=0     Sep 2002 RepÃºblica de California 2×59×83 Posts The bit about using the proposed algorithm to "slow down the execution of many factoring programs" is just precious. Perhaps he's having a problem with his Pee Cee overheating when it runs a factoring-program-written-by-someone-clueful?

 Similar Threads Thread Thread Starter Forum Replies Last Post MattcAnderson Homework Help 5 2016-11-01 08:16 Triber Computer Science & Computational Number Theory 17 2015-11-10 17:48 MattcAnderson Puzzles 8 2014-12-05 15:09 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 00:51.

Wed Oct 28 00:51:15 UTC 2020 up 47 days, 22:02, 2 users, load averages: 2.12, 2.36, 2.14