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()
{
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 < 13)
{
_timeHelper = System.currentTimeMillis();
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);
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");
_timeHelper = System.currentTimeMillis();
while(i < 100000)
{
_result2 = _mf.multBaseKBit(_a, _b, 4);
_overallResult.add(_result2);
i++;
}
_time2 = System.currentTimeMillis()-_timeHelper;
i=0;
_timeHelper = System.currentTimeMillis();
while(i < 100000)
{
_result = _mf.multSchulmethode(_a, _b);
_overallResult.add(_result);
i++;
}
_time1 = System.currentTimeMillis()-_timeHelper;
i =0;
_timeHelper = System.currentTimeMillis();
while(i < 100000)
{
_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");
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()
{
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 < 13)
{
_timeHelper = System.currentTimeMillis();
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);
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");
_timeHelper = System.currentTimeMillis();
while(i < 100000)
{
_result2 = _mf.multBaseKBit(_a, _b, 4);
_overallResult.add(_result2);
i++;
}
_time2 = System.currentTimeMillis()-_timeHelper;
i=0;
_timeHelper = System.currentTimeMillis();
while(i < 100000)
{
_result = _mf.multSchulmethode(_a, _b);
_overallResult.add(_result);
i++;
}
_time1 = System.currentTimeMillis()-_timeHelper;
i =0;
_timeHelper = System.currentTimeMillis();
while(i < 100000)
{
_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)
{
_result = _mf.multSchulmethode(_a, _b);
_overallResult.add(_result);
i++;
}
_time1 = System.currentTimeMillis()-_timeHelper;
i =0;
_timeHelper = System.currentTimeMillis();
while(i < _limiter)
{
_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");
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]);
}
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;
}
}