наш препод придумал задание - написать аналог BigInteger
вот пишу деление:
| Код |
public class MamontInteger {
/**
* @param args the command line arguments
*/
private int num[];
private final static long LONG_MASK = 0xffffffffL;
public final static MamontInteger ZERO = new MamontInteger("0");
public final static MamontInteger ONE = new MamontInteger("1");
//...
|
процедура
| Код |
//избавление от лишних начальных нулевых значений в массиве
private static int[] trustedStripLeadingZeroInts(int val[]) {
int byteLength = val.length;
int keep;
// Find first nonzero byte
for (keep=0; keep<val.length && val[keep]==0; keep++);
if (keep > 0) {
int result[] = new int[val.length - keep];
for(int i=0; i<val.length - keep; i++)
result[i] = val[keep+i];
return result;
}
return val;
}
|
и еще 2
| Код |
static int nlz (int x)
{
int y;
int n;
n = 32;
y = x >>> 16; if (y!=0) {n = n-16; x=y;}
y = x >>> 8; if (y!=0) {n = n-8; x=y;}
y = x >>> 4; if (y!=0) {n = n-4; x=y;}
y = x >>> 2; if (y!=0) {n = n-2; x=y;}
y = x >>> 1; if (y!=0) return n-2;
return n-x;
}
//делит беззнаково long на беззнаковое int
private void divWord(int[] result, long n, int d)
{
long dLong = d & LONG_MASK;
if (dLong == 1) {
result[0] = (int)n;
result[1] = 0;
return;
}
// Approximate the quotient and remainder
long q = (n >>> 1) / (dLong >>> 1);
long r = n - q*dLong;
// Correct the approximation
while (r < 0) {
r += dLong;
q--;
}
while (r >= dLong) {
r -= dLong;
q++;
}
// n - q*dlong == r && 0 <= r <dLong, hence we're done.
result[0] = (int)q;
result[1] = (int)r;
}
|
| Код |
public MamontInteger divide(MamontInteger val, MamontInteger rem)
{
long qhat,rhat,k,p, t;
int[] qWord = new int[2];
long b = 0x100000000L;
if (compareTo(val) < 0)
{
rem = this;
return MamontInteger.ZERO;
}
int m = this.num.length;
int n = val.num.length;
rem.num = new int[n]; //остаток
if (n ==1)
return this.divide(val.num[0], rem.num);
int[] u = new int[m]; //развернутый 1 массив
for (int i=0; i<m; i++)
u[i] = this.num[m-1-i];
int[] v = new int[n]; //развернутый 2 массив
for (int i=0; i<n;i++)
v[i] = val.num[n-1-i];
int[] q = new int[m]; //частное
int s = 32 - nlz(v[0]);
int vn[] = new int[n];
for (int i=n-1; i>0; i--)
vn[i] = (v[i] << s) | (v[i-1] >>> (32-s));
vn[0] = v[0] << s;
int[] un = new int[m+1];
un[m] = u[m-1] >>> (32-s);
for (int i=m-1; i>0; i--)
un[i] = (u[i] << s) | (u[i-1] >>> (32-s));
un[0] = u[0] << s;
for (int j=m-n; j>=0; j--)
{
boolean skipCorrection = false;
int nh = un[j+n];
int nh2 = nh + 0x80000000;
rhat = un[j+n] & LONG_MASK;
rhat = (rhat << 32) | (un[j+n-1] & LONG_MASK);
if (rhat >=0)
{
qhat = rhat / (vn[n-1] & LONG_MASK);
long q2 = qhat * (vn[n-1] & LONG_MASK);
rhat -= q2;
}
else
{
divWord(qWord, rhat, vn[n-1]);
qhat = qWord[0];
rhat = qWord[1];
}
if (qhat == 0)
continue;
while (true)
{
if (qhat >=b || qhat*(vn[n-2] & LONG_MASK) > b*rhat + (un[j+n-2] & LONG_MASK))
{
qhat = qhat - 1;
rhat = rhat + (vn[n-1] & LONG_MASK);
if (rhat <b)
continue;
}
k=0;
for (int i=0; i<n; i++)
{
p = qhat*(vn[i] & LONG_MASK);
t = (un[i+j] & LONG_MASK)-k;
t -= (p & LONG_MASK);
un[i+j] = (int) t;
k = (p >>> 32) - (t >>> 32);
}
t = (un[j+n] & LONG_MASK) - k;
un[j+n] = (int) t;
//сохраняем очередную цифру
q[j] = (int) qhat;
if (t<0)
{
q[j] = q[j] - 1;
k=0;
for (int i=0; i<n; i++)
{
t = (un[i+j] & LONG_MASK) + (vn[i] & LONG_MASK) + k;
un[i+j] = (int) t;
k = (t & LONG_MASK) >>> 32;
}
un[j+n] = (int) ((un[j + n] & LONG_MASK) + k);
}
break;
}
} //for j
for (int i=0; i<n; i++)
rem.num[n-i-1] = (un[i] >>> s) | (un[i+1] << (32-s));
rem.num = trustedStripLeadingZeroInts(rem.num);
int [] qr = new int[q.length];
for (int i=0; i<qr.length ;i++)
qr[i] = q[m-i-1];
qr = trustedStripLeadingZeroInts(qr);
return new MamontInteger(qr);
|
процедура деления когда делитель состоит из одного числа int работает 100% (public MamontInteger divide (int val, int[] r))
код процедуры деления больших чисел взял из книги:
Алгоритмические трюкт для программистов
Henry S. Warren, Jr
http://turbanoff.narod.ru/algtruc.djvu страницы 142-144
там код на с, переделывал с учетом особнностей java.
Что то не доглядел. мб у кого дойдут руки посмотреть. ну или мб напрваите меня на путь истинный, а то от отладчика уже голова болит...
да исходники моего класса (проект NetBeans)
http://turbanoff.narod.ru/MamontInteger.rar
|