Java - Multiplication Functions

Question

4.00/5 (1 vote)

See more:

Hi there,

yes this is indeed a "HOMEWORK"-related Question, i know one should not ask about such things, but i encountered some strange behaviour with my programm.

The programm should multiply with 2 different functions and i have to compare the runtimes to see which one is better.

The first function is a simply multiply of 2 big Numbers (therefore BigInteger), the second one works like a know algorithm (can't remember the name).

~~1st Problem, my "faster" algorithm (the second one) is quite slow :/~~

~~2nd Problem, in my other machine i get a heap execption.~~
Solved, by using smaller k, i understand a k of 256 is to big even for BigInt inf pow'ed up and used for an array...

My question, can anyone tell me where my code is wrong?
I just don't understand it.

Programm given:
Main

import java.math.BigInteger;


public class Main {

	public static void main(String[] args) {
		
		new Main();

	}

	public Main()
	{
		//Initializations
		MultiplyFunctions _mf = new MultiplyFunctions();
		BigInteger _a = new BigInteger("1231204469812315648641321537684894132157869");
		BigInteger _b = new BigInteger("8923743168465219846541651325714897463137897");
		BigInteger _result2 = null, _result = null, _result3 = null;
		double _time1 = 0, _time2 = 0, _time3 = 0, _timeHelper = 0;
		
		int i = 2;
		//while( i < (_b.bitLength()/4))
		
		//First test, which K is best for this multiplication
		while( i < 13)
		{	
			//MultBaseKBit			
			_timeHelper = System.currentTimeMillis();
			//TO get some time values we run this multiplication 100000 times
			for(int x = 0; x < 100000; x++)
			{
			_result2 = _mf.multBaseKBit(_a, _b, i);
			}
			_time2 = System.currentTimeMillis()-_timeHelper;
			
			System.out.println("***** K = " + i + " *****" + "\t Zeit: " + _time2);			
			i++;
		}
		
		System.out.println("********************************");
		System.out.println("Ergebnis von KBit  : " + _result2);	
		
		//Look up in the predefined K table and choose best K
		int[] _kTable = {0,2,19,68,225,658,1813,4808,12333,30770,75163,
				180308,426075,994070,2293895,5243024,11884037,26738886,59769041};
		int n = _b.bitLength();
		int k = 1;
		while((k<_kTable.length) && (_kTable[k]<n))
		{
			k++;
		}
		
		BigInteger _overallResult = new BigInteger("0");
		
		//Calculations
		_timeHelper = System.currentTimeMillis();
		while(i < 100000)
		{
			//MultBaseKBit					
			_result2 = _mf.multBaseKBit(_a, _b, 4);	
			_overallResult.add(_result2);
			i++;
		}
		_time2 = System.currentTimeMillis()-_timeHelper;
		i=0;
		
		_timeHelper = System.currentTimeMillis();
		while(i < 100000)
		{
			//Schul			
			_result =  _mf.multSchulmethode(_a, _b);	
			_overallResult.add(_result);
			i++;
		}
		_time1 = System.currentTimeMillis()-_timeHelper;
		i =0;
		
		_timeHelper = System.currentTimeMillis();
		while(i < 100000)
		{
			//OptK			
			_result3 = _mf.multBaseKBit(_a, _b, k);	
			_overallResult.add(_result3);
			i++;
		}
		_time3 = System.currentTimeMillis()-_timeHelper;
		
		System.out.println("********************************");
		System.out.println("Ergebnis von KBit  : " + _result2);
		System.out.println("Zeit: " + _time2);	

		System.out.println("********************************");
		System.out.println("Ergebnis von Schul : " + _result);
		System.out.println("Zeit: " + _time1);
		
		System.out.println("********************************");
		System.out.println("Optimiertes K");
		System.out.println("Ergebnis 3: " + _result3);
		System.out.println("Zeit: " + _time3);
		
		System.out.println(_overallResult);
	}
}

Multiply Functions

import java.math.*;
import java.util.*;

public class MultiplyFunctions {
	
	public BigInteger multSchulmethode(BigInteger a, BigInteger b)
	{
		BigInteger _result = new BigInteger("0");
		BigInteger _preResult = new BigInteger("0");
		
		//Multiplikation
		for(int i = 0; i < b.bitLength(); i++)
		{
			if(b.testBit(i))
			{
			_preResult = a;
			_preResult = _preResult.shiftLeft(i);
			_result = _result.add(_preResult);
			}			
		}		
		return _result;
	}
	
	public BigInteger multBaseKBit(BigInteger a, BigInteger b, int k)
	{
		int _kIs = (int)Math.pow(2,k);
		BigInteger _result = new BigInteger("0");
		BigInteger _preResult = new BigInteger("0");
		BigInteger[] _kArray = new BigInteger[_kIs];
		
		_kArray[0] = new BigInteger("0");
		for(int i = 1; i < _kIs; i++)
		{
			_kArray[i] = a.add(_kArray[i-1]);
		}
		
		for(int i = 0; i < b.bitLength(); i+=k)
		{
			int _bitErg = 0;
			for(int x = 0; x < k; x++)
			{				
				if(b.testBit(i+x)) {_bitErg += Math.pow(2, x);}
			}
			_preResult = _kArray[_bitErg];
			_preResult = _preResult.shiftLeft(i);
			_result = _result.add(_preResult);
		}
		
		return _result;
	}

}

Well i managed my self by using a mask instead of the _bitErg. It is now faster and shows its power at numbers > 800 bit legth by consuming only 50% time of the common multiply algorithm.

Nevertheless thanks for reading this Question :)

EDIT: As announced complete programm down here

import java.math.BigInteger;


public class Main {

	public static void main(String[] args) {
		
		new Main();

	}

	public Main()
	{
		//Initializations
		MultiplyFunctions _mf = new MultiplyFunctions();
		BigInteger _a = new BigInteger("1231204469812315648641321537684894132157869");
		BigInteger _b = new BigInteger("8923743168465219846541651325714897463137897");
		BigInteger _result2 = null, _result = null, _result3 = null;
		double _time1 = 0, _time2 = 0, _time3 = 0, _timeHelper = 0;
		
		int i = 2;
		//while( i < (_b.bitLength()/4))
		
		//First test, which K is best for this multiplication
		while( i < 13)
		{	
			//MultBaseKBit			
			_timeHelper = System.currentTimeMillis();
			//TO get some time values we run this multiplication 100000 times
			for(int x = 0; x < 100000; x++)
			{
			_result2 = _mf.multBaseKBit(_a, _b, i);
			}
			_time2 = System.currentTimeMillis()-_timeHelper;
			
			System.out.println("***** K = " + i + " *****" + "\t Zeit: " + _time2);			
			i++;
		}
		
		System.out.println("********************************");
		System.out.println("Ergebnis von KBit  : " + _result2);	
		
		//Look up in the predefined K table and choose best K
		int[] _kTable = {0,2,19,68,225,658,1813,4808,12333,30770,75163,
				180308,426075,994070,2293895,5243024,11884037,26738886,59769041};
		int n = _b.bitLength();
		int k = 1;
		while((k<_kTable.length) && (_kTable[k]<n))
		{
			k++;
		}
		
		BigInteger _overallResult = new BigInteger("0");
		
		//Calculations
		_timeHelper = System.currentTimeMillis();
		while(i < 100000)
		{
			//MultBaseKBit					
			_result2 = _mf.multBaseKBit(_a, _b, 4);	
			_overallResult.add(_result2);
			i++;
		}
		_time2 = System.currentTimeMillis()-_timeHelper;
		i=0;
		
		_timeHelper = System.currentTimeMillis();
		while(i < 100000)
		{
			//Schul			
			_result =  _mf.multSchulmethode(_a, _b);	
			_overallResult.add(_result);
			i++;
		}
		_time1 = System.currentTimeMillis()-_timeHelper;
		i =0;
		
		_timeHelper = System.currentTimeMillis();
		while(i < 100000)
		{
			//OptK			
			_result3 = _mf.multBaseKBit(_a, _b, k);	
			_overallResult.add(_result3);
			i++;
		}
		_time3 = System.currentTimeMillis()-_timeHelper;
		
		System.out.println("\n");
		System.out.println("Ergebnis von KBit  : " + _result2 + "\t Zeit: " + _time2);
		System.out.println("\n");	

		System.out.println("Ergebnis von Schul : " + _result + "\t Zeit: " + _time1);
		System.out.println("\n");
		
		System.out.println("********************************");
		System.out.println("Optimiertes K");
		System.out.println("Ergebnis 3: " + _result3);
		System.out.println("Zeit: " + _time3);
		
		System.out.println(_overallResult);
		System.out.println(_a.multiply(_b));
		
		int _limiter = 100000;
		for(int y = 0; y < 15; y++)
		{
			if(y==3) {_limiter = 10000;}
			if(y==7){_limiter = 1000;}
			n = _b.bitLength();
			k = 1;
			while((k<_kTable.length) && (_kTable[k]<n))
			{
				k++;
			}
			
			i = 0; 
			_timeHelper = System.currentTimeMillis();
			while(i < _limiter)
			{
				//Schul			
				_result =  _mf.multSchulmethode(_a, _b);	
				_overallResult.add(_result);
				i++;
			}
			_time1 = System.currentTimeMillis()-_timeHelper;
			i =0;
			
			_timeHelper = System.currentTimeMillis();
			while(i < _limiter)
			{
				//OptK			
				_result3 = _mf.multBaseKBit(_a, _b, k);	
				_overallResult.add(_result3);
				i++;
			}
			_time3 = System.currentTimeMillis()-_timeHelper;
			
			System.out.println("k: " + k + "\t n: " + n + "\t \t tschul: " + _time1 + "\t \t tkbit: " + _time3 + "\t \t Faktor: " + (_time3/_time1));
			
			_a = _a.multiply(_b);
			_b = _b.multiply(new BigInteger("13172478124671294127213124871268727412"));
		}
		System.out.println(_overallResult);
	}
}

import java.math.*;
import java.util.*;

public class MultiplyFunctions {
	
	public BigInteger multSchulmethode(BigInteger a, BigInteger b)
	{
		BigInteger _result = new BigInteger("0");
		BigInteger _preResult = new BigInteger("0");
		
		//Multiplikation
		for(int i = 0; i < b.bitLength(); i++)
		{
			if(b.testBit(i))
			{
			_preResult = a;
			_preResult = _preResult.shiftLeft(i);
			_result = _result.add(_preResult);
			}			
		}		
		return _result;
	}
	
	public BigInteger multBaseKBit(BigInteger a, BigInteger b, int k)
	{
		//Initialisierung
		int _kIs = (int)Math.pow(2,k);
		BigInteger _result = new BigInteger("0");
		BigInteger _preResult = new BigInteger("0");
		BigInteger[] _kArray = new BigInteger[_kIs];
		//char[] _bArray = b.toString(2).toCharArray();	
		
		//Initialisiere kArray
		_kArray[0] = new BigInteger("0");
		for(int i = 1; i < _kIs; i++)
		{
			_kArray[i] = a.add(_kArray[i-1]);			
		}		
		
		BigInteger _mask = new BigInteger("0");
		for(int i= 0; i < k; i++)
		{			
			_mask = _mask.flipBit(i);
		}
		
		int _shifter = 0;
		
		while(b.bitLength() > 0)
		{		
			int tst = b.and(_mask).intValue();
			b = b.shiftRight(k);
			_preResult = _kArray[tst];
			_preResult = _preResult.shiftLeft(_shifter);
			_result = _result.add(_preResult);
			
			_shifter += k;
		}
				
		return _result;
	}
	
	/*int _counter = 0;
	int _shifter = 0;
	BigInteger _number = new BigInteger("0");
	for(int i = 0; i <_bArray.length; i++)
	{
		//Solange der zähler unter K lese nächstes bit
		if(_counter < k)
		{
			if(_bArray[_bArray.length-1-i] == '1')
			{
				_number = _number.flipBit(_counter);
			}
			_counter++;
		}
		//Wenn der Zähler = k oder wir am ende sind führe addition + shift aus
		if(_counter == k || i == _bArray.length-1)
		{
		_preResult = _kArray[_number.intValue()];
		_preResult = _preResult.shiftLeft(_shifter);
		_result = _result.add(_preResult);
		_number = new BigInteger("0");
		_counter = 0;
		_shifter += k;
		}
	}
	*/
	
	/*for(int i = 0; i < b.bitLength(); i+=k)
	{						
		//if(b.testBit(i)) {_bitErg += (int) Math.pow(2, x); x++;}
		try{
		_preResult = _kArray[Integer.parseInt((_bAsBits.substring(i, i+k)),2)];
		}
		catch(Exception ex)
		{ _preResult = _kArray[Integer.parseInt((_bAsBits.substring(i)),2)];}
		_preResult = _preResult.shiftLeft(i);
		_result = _result.add(_preResult);
		//_bitErg = 0;
		
	}		
	*/

}

Posted 24-Mar-15 5:27am

HobbyProggy

Updated 15-Apr-15 5:43am

v6

Add a Solution

Comments

Jörgen Andersson 24-Mar-15 14:01pm

It's the double loop that does it

HobbyProggy 25-Mar-15 4:40am

How could i make it more efficient?

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

HobbyProggy · Accepted Answer · 2015-04-15T02:22:00

Solved by myself using a mask.

First of all the "crucial" partof the code. The function got a "complete" rework.

Java

public BigInteger multBaseKBit(BigInteger a, BigInteger b, int k)
	{
		//Initialisierung
		int _kIs = (int)Math.pow(2,k);
		BigInteger _result = new BigInteger("0");
		BigInteger _preResult = new BigInteger("0");
		BigInteger[] _kArray = new BigInteger[_kIs];
		//char[] _bArray = b.toString(2).toCharArray();	
		
		//Initialisiere kArray
		_kArray[0] = new BigInteger("0");
		for(int i = 1; i < _kIs; i++)
		{
			_kArray[i] = a.add(_kArray[i-1]);			
		}		
		
		BigInteger _mask = new BigInteger("0");
		for(int i= 0; i < k; i++)
		{			
			_mask = _mask.flipBit(i);
		}
		
		int _shifter = 0;
		
		while(b.bitLength() > 0)
		{		
			int tst = b.and(_mask).intValue();
			b = b.shiftRight(k);
			_preResult = _kArray[tst];
			_preResult = _preResult.shiftLeft(_shifter);
			_result = _result.add(_preResult);
			
			_shifter += k;
		}
				
		return _result;
	}

The basics stay the same -> Initializing variables and creating the K array which stores the precalculated result of a.
e.g. for a k = 2 the array gets 4 slots / array[0] = 0, array[1] = array[0]+a, array[2] = array[1]+a and so on.

Then the new part begins, accoring to my k i initialize a mask (BigInteger).
With this mask we run through the b's bit length while we get the int value for the array (e.g. we say k = 2, we mask with 11b and get a result between 0-3) and shift b to the right* by k's value.

Then the preresults gets filled with the arrays value and finally shifted by the amount we already shifted b to the right (basically k*timesWeLooped).
After shifting we add the preresult to the result and add k to the shifter.

That's the faster way to do which shows that this algorithm is more efficient than the already good basic method. The real strength of this algorithm is shown when bit length is above 800, we get a factor of 50% time compared to the basic method.

Hope this solution helps other people ;)

BTW: Added the complete code to the question, so everybody can see for himself ;)