VPF::деление больших чисел - Форум программистов

turbanoff

Дата 16.5.2009, 19:16 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 57
Регистрация: 6.4.2009

Репутация: нет
Всего: 1

наш препод придумал задание - написать аналог 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
вот она страницы 142-144
там код на с, переделывал с учетом особнностей java.
Что то не доглядел. мб у кого дойдут руки посмотреть. ну или мб напрваите меня на путь истинный, а то от отладчика уже голова болит...

да исходники моего класса (проект NetBeans)
http://turbanoff.narod.ru/MamontInteger.rar

dEEp

Дата 21.5.2009, 19:10 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 58
Регистрация: 9.5.2007

Репутация: нет
Всего: нет

что именно не доглядел? что там за циклы внутри без комментов? что за ошика выдаётся? где именно проблема?

нифига не понятно.

GirroKepasso

Дата 21.5.2009, 22:28 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 5
Регистрация: 7.7.2008

Репутация: нет
Всего: нет

А вобще не факт, что исходники из книги работали коректно(ошибка в типографии или автор не проверил в живую).
Я б на твоем месте ,написал бы юнит тесты (от протсых примеров к более сложным) и проверял бы свой код через BigInteger.

Кстати с удивлением обнаружил (со слов автора книги), что деление столбиком сложнее реализовать в сравнении с его способом.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Java: Общие вопросы \| Следующая тема »