Java - 乘法函数 [英] Java - Multiplication Functions
问题描述
你好，
是的，这确实是家庭作业相关的问题，我知道不应该问这样的事情，但是我的程序遇到了一些奇怪的行为。
程序应该乘以2个不同的函数，我必须比较运行时间，看看哪个更好。
第一个函数是简单乘以2个大数字（因此是BigInteger），第二个函数就像一个知道算法（不记得名字）。 />
第一个问题，我的更快算法（第二个）非常慢：/
第二个问题，在我的另一台机器上我得到了一个堆执行。
解决了，通过使用更小的k，我理解256的ak是即使对于BigInt inf也很大并用于阵列...
我的问题，谁能告诉我我的代码错在哪里？
我只是不明白。
程序给出：
Main
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;
}
}
我通过使用面具代替_bitErg来管理我的自我。它现在更快，并且在数字>处显示其功率。通过仅占用普通乘法算法的50％时间来获得800位长度。
不过感谢您阅读此问题:)
编辑：正如宣布的完整程序在这里
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 :)
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;
}
*/
}
推荐答案
解决方案我自己戴着面具。
首先是代码的关键部分。该函数得到了完整的返工。
Solved by myself using a mask.
First of all the "crucial" partof the code. The function got a "complete" rework.
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;
}
基本保持不变 - >初始化变量并创建K数组，该数组存储a。
的预先计算结果，例如：对于ak = 2，数组得到4个槽/数组[0] = 0，数组[1] =数组[0] + a，数组[2] =数组[1] + a等等。
然后新的部分开始，根据我的ki初始化一个掩码（BigInteger）。
使用这个掩码，当我们得到int时，我们运行b的位长度数组的值（例如我们说k = 2，我们用11b掩码并得到0-3之间的结果）并将b向右移*乘以k的值。
然后preresults填充数组值，最后移动我们已经向右移动的数量b（基本上是k * timesWeLooped）。
移位后我们将preresult添加到结果并添加转向移位器。
这是更快的方法，表明这种算法比已经很好的基本方法更有效。当比特长度超过800时，显示该算法的真正强度，与基本方法相比，我们获得50％的时间因素。
希望此解决方案能够帮助其他人们;）
BTW：在问题中添加了完整的代码，所以每个人都可以亲眼看看;）
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 ;)
这篇关于Java - 乘法函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
