mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2007-12-15, 10:18   #1
vector
 
vector's Avatar
 
Nov 2007
home

52 Posts
Default 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) {

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());
}
}
vector is offline   Reply With Quote
Old 2007-12-15, 11:18   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

22·32·281 Posts
Default

Quote:
Originally Posted by vector View Post
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
xilman is online now   Reply With Quote
Old 2007-12-15, 12:50   #3
vector
 
vector's Avatar
 
Nov 2007
home

2510 Posts
Default

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

   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());

}
}
vector is offline   Reply With Quote
Old 2007-12-15, 13:44   #4
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

2×2,971 Posts
Default

Again, the question is why?
rogue is online now   Reply With Quote
Old 2007-12-15, 14:12   #5
vector
 
vector's Avatar
 
Nov 2007
home

52 Posts
Default

Why what?
vector is offline   Reply With Quote
Old 2007-12-15, 17:04   #6
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

2·2,971 Posts
Default

Quote:
Originally Posted by vector View Post
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".
rogue is online now   Reply With Quote
Old 2007-12-15, 19:59   #7
vector
 
vector's Avatar
 
Nov 2007
home

52 Posts
Default

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.
vector is offline   Reply With Quote
Old 2007-12-15, 20:52   #8
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

25·7·11 Posts
Default

Moved to Misc. Math.

Alex
akruppa is offline   Reply With Quote
Old 2007-12-19, 14:30   #9
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

31·43 Posts
Default

Quote:
Originally Posted by vector View Post
... 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.
alpertron is offline   Reply With Quote
Old 2007-12-20, 15:03   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by vector View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2007-12-20, 18:16   #11
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

9,791 Posts
Default

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?
ewmayer 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
Possible better multiplication algorithm Triber Computer Science & Computational Number Theory 17 2015-11-10 17:48
5 digit multiplication MattcAnderson Puzzles 8 2014-12-05 15:09
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 20:02.

Thu Oct 22 20:02:58 UTC 2020 up 42 days, 17:13, 1 user, load averages: 1.44, 2.05, 1.97

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.