mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)
-   -   New Multiplication Algorithm (https://www.mersenneforum.org/showthread.php?t=9743)

vector 2007-12-15 10:18

New Multiplication Algorithm
 
I just coded a new multiplication algorithm which slower than trial multiplication :smile:
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) {

ArrayList<BigInteger>primes=new ArrayList<BigInteger>();
ArrayList<BigInteger>resedues=new ArrayList<BigInteger>();
ArrayList<BigInteger>moduli=new ArrayList<BigInteger>();
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;i<primes.size();i++){
BigInteger prime1=primes.get(i);
if(number1.gcd(prime1).equals(one)){
if(number2.gcd(prime1).equals(one)){
BigInteger resedue1=number1.mod(prime1);
BigInteger resedue2=number2.mod(prime1);
BigInteger reseduetotal=resedue1.multiply(resedue2).mod(prime1);
//System.out.println("resedue: "+reseduetotal+" mod "+prime1);
resedues.add(reseduetotal);
moduli.add(prime1);
compositemod=compositemod.multiply(prime1);
if(compositemod.bitLength()>totallength){
i=primes.size();
}
}
}
}

BigInteger x=zero;
for(int i=0;i<resedues.size();i++){
BigInteger partinverse=compositemod.divide(moduli.get(i));
BigInteger inverseb=partinverse.modInverse(moduli.get(i));
BigInteger solutioni=partinverse.multiply(inverseb).multiply(resedues.get(i));
x=x.add(solutioni);
}
x=x.mod(compositemod);
end=System.nanoTime()-start;
System.out.println("fast multpliction time: "+end+"ns");
System.out.println("fast multiplication: "+x);
System.out.println("bitlength: "+x.bitLength());
}
}[/code]

xilman 2007-12-15 11:18

[QUOTE=vector;120756]I just coded a new multiplication algorithm which slower than trial multiplication :smile:
It is in java code.[/QUOTE]Why?

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

Paul

vector 2007-12-15 12:50

Ok I commented the code. :rolleyes:

[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) {

ArrayList<BigInteger>primes=new ArrayList<BigInteger>();//list of primes
ArrayList<BigInteger>resedues=new ArrayList<BigInteger>();//list of resedues
ArrayList<BigInteger>moduli=new ArrayList<BigInteger>();//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;i<primes.size();i++){
BigInteger prime1=primes.get(i);//get prime from prime list
if(number1.gcd(prime1).equals(one)){//check that prime is not a
if(number2.gcd(prime1).equals(one)){//factor of either numbers
BigInteger resedue1=number1.mod(prime1);//mod first multiplicand by the prime
BigInteger resedue2=number2.mod(prime1);//mod second multiplicand by the prime
BigInteger reseduetotal=resedue1.multiply(resedue2).mod(prime1);
//multiply resedue together and mod them to the prime
//System.out.println("resedue: "+reseduetotal+" mod "+prime1);//debug
resedues.add(reseduetotal);//store product resedue in resedue list
moduli.add(prime1);//add used prime to moduli list
compositemod=compositemod.multiply(prime1);
if(compositemod.bitLength()>totallength){//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<resedues.size();i++){
BigInteger partinverse=compositemod.divide(moduli.get(i));
BigInteger inverseb=partinverse.modInverse(moduli.get(i));
BigInteger solutioni=partinverse.multiply(inverseb).multiply(resedues.get(i));
x=x.add(solutioni);
}
x=x.mod(compositemod);//x is the product

//this is the analysis part
end=System.nanoTime()-start;
System.out.println("fast multpliction time: "+end+"ns");
System.out.println("fast multiplication: "+x);
System.out.println("bitlength: "+x.bitLength());

}
}[/code]

rogue 2007-12-15 13:44

Again, the question is why?

vector 2007-12-15 14:12

Why what?

rogue 2007-12-15 17:04

[QUOTE=vector;120769]Why what?[/QUOTE]

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".

vector 2007-12-15 19:59

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. :missingteeth: 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.:blahblah:

akruppa 2007-12-15 20:52

Moved to Misc. Math.

Alex

alpertron 2007-12-19 14:30

[QUOTE=vector;120795]... 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.:blahblah:[/QUOTE]

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.

R.D. Silverman 2007-12-20 15:03

[QUOTE=vector;120795]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. :missingteeth: 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.:blahblah:[/QUOTE]


Clueless. :missingteeth::w00t::bs meter::rtfm:

ewmayer 2007-12-20 18:16

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?


All times are UTC. The time now is 03:59.

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