VPF::Длинное нецелочисленое деление

Hohhi

Дата 30.3.2008, 17:55 (ссылка)

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

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 171
Регистрация: 25.2.2006
Где: Молдова

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

Привет всем! Нужно поделить два длинных числа, при этом деля не целочисленно, а с определенной точностью. Например: 6/4=1,5
Написана процедура целочисленного деления

Код


#define o 10L
void d_l(int *a1, int *a2, int *rez)
{
    int *prez, *pa1=a1+*a1, *pa2=*a2+a2,*mid;
    if (((*a1)-(*a2))>=0)
    {
        mid=a1+*a1-*a2;
        *rez=*a1-*a2+1;
    }
    else
    {
        *rez=1;
        rez[1]=0;
        return;
    }
    prez=rez+*rez;
    while (prez>rez)
    {
        if (*a2>pa1-mid||(*a2==pa1-mid)&&les(mid,a2)==1)
        {
            *prez--=0;
            mid--;
            continue;
        }
        if(*a2==pa1-mid)
        {
            (*a1)++;
            pa1++;
        }
        *prez=( (double)o*o*(*pa1)+o*( *(pa1-1) ) + *(pa1-2) )/( o*(*pa2)+(*(pa2-1))+1 );
        sub(mid,*prez,a2);
        if (les(mid,a2)!=1)
        {
            (*prez)++;
            sub(mid,1,a2);
        }
        while(*pa1==0&&pa1>a1)
        {
            pa1--;
            --*a1;
        }
        prez--;
        mid--;
    }
    if (rez[*rez]==0)

        --*rez;
}

int les(int *mid,int *a2)
{
    int i=*a2;
    if (mid[i+1])
        return 0;
    while (i&&mid[i]==a2[i])
        i--;
    if (i==0)
        return 0;
    else
        return(mid[i]<a2[i]);
}
void sub(int *a1,int q,int *a2)
{
    int i=1;
    while (i<=*a2)
    {
        a1[i]-=(long)q*a2[i]%o;
        a1[i+1]-=(long)q*a2[i]/o;
        while(a1[i]<0)
        {
            a1[i]+=o;
            a1[i+1]-=1;
        }
        i++;
    }
    while(i<=*a1)
    {
        while(a1[i]<0)
        {
            a1[i]+=o;
            a1[i+1]-=1;
        }
        i++;
    }

идея у меня была такова, сдвинуть элементы массива вправо, поделить, получить результат, переписать его в удобной форме.
вот код сдвига массива(вместе с нулевым элементом):

Код


void revers(int mas[],int j,int n)
{
    int buff;
    if (j==(n/2)+1)
    {
        buff=mas[j];
        mas[j]=mas[j+1];
        mas[j+1]=buff;
    }
    for (int i = j; i < (n/2)+1; i++)
     {
        buff = mas[(n)+j-i];
        mas[(n)-i+j] = mas[i];
          mas[i] = buff;
      }
}
void shift(int mas[],int i,int n)
{
    revers(mas,0,i-1);
    revers(mas,i,n-1);
    revers(mas,0,n-1);
}

Всё пробую реализовать этот алгоритм, но в конечном итоге бьюсь о smile

как представлены у меня в процедуре числа, допустим у нас число 123456789:
а) при о==10L массив{9,9,8,7,6,5,4,3,2,1}
б)при о=10000L массив {3,6789,2345,1,0}
то есть переворачиваем число и делим на группы.(чем больше о, тем эффективнее алгоритм)

Моя конечная цель написать метод Гаусса для большой арифметики, попросили сделать, но с делением у меня ступор.

Народ, помогите, кто чем может, идеей, алгоритмом, псевдокодом!
Заранее благодарю

creatorcode

Дата 30.3.2008, 18:32 (ссылка)

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

Загрузка ...

Шустрый

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

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

http://algolist.manual.ru/maths/longnum.php

Hohhi

Дата 30.3.2008, 18:57 (ссылка)

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

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 171
Регистрация: 25.2.2006
Где: Молдова

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

creatorcode, Спасибо, статья действительно интересная, я её уже читал, но там только про целочисленное деление

creatorcode

Дата 30.3.2008, 19:06 (ссылка)

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

Загрузка ...

Шустрый

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

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

Почитай Кнута, 2-ой том "Получисленные алгоритмы".

Alexandr87

Дата 30.3.2008, 19:08 (ссылка)

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

Загрузка ...

дыкий псых

Профиль
Группа: Завсегдатай
Сообщений: 1459
Регистрация: 27.11.2004
Где: Алматы, Казахстан

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

столбиком?

Цитата(Hohhi @ 30.3.2008, 20:55

)

как представлены у меня в процедуре числа, допустим у нас число 123456789:
а) при о==10L массив{9,9,8,7,6,5,4,3,2,1}
б)при о=10000L массив {3,6789,2345,1,0}

странно это все как-то.
Почитайте про представление дробных чисел в памяти компьютера. Отдельные разряды представляют порядок, отдельные - мантису.

Hohhi

Дата 31.3.2008, 10:15 (ссылка)

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

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 171
Регистрация: 25.2.2006
Где: Молдова

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

Alexandr87, Всё ок, это так называемая обратная форма представления. посмотри сколь просто алгорит суммы и произведения

Код


void suma(long *a,long *b,long *sum)
{
    int i,perenos=0;
    if (a[0]>b[0])
        sum[0]=a[0];
    else
        sum[0]=b[0];
    for (i=1;i<=sum[0];i++)
    {
        sum[i]=a[i]+b[i]+perenos;
        perenos=sum[i]/o;
        sum[i]=sum[i]%o;
    }
    if (perenos!=0)
    {
    sum[0]++;
    sum[sum[0]]=1;
    }
}

void proizvedenie(long* a,long* b,long* proizv)
{
    int nulei=0,i,j,k;

    for(j=1;j<b[0]+1;j++)
    {
        long pr[100]={0};int snosim=0;


        pr[0]=a[0];
        for(k=0;k<nulei;k++)
        {
            pr[0]++;
        }
        for(i=1;i<a[0]+1;i++)
        {
            pr[i+k]=a[i]*b[j]+snosim;
            snosim=pr[i+k]/o;
            pr[i+k]=pr[i+k]%o;

        }
            if (snosim!=0)
        {
        pr[0]++;
        pr[pr[0]]=snosim;
        }
        ++nulei;
        suma(pr,proizv,proizv);
    }
}

деление сделал, кому интересно,добавил функцию сравнения чисел

Код


int sravn(long* a,long* b)
{
    if (a[0]<b[0])
        return 1;
    else if(a[0]>b[0])
        return 0;
    else
    {
        int f=a[0],s=b[0];
        while (1)
        {
            if (a[f]<b[s])
                return 1;
            else if (a[f--]>b[s--])
                return 0;
            if (!f) return -1;
        }

    }
}

в мэйне написал:

Код


int c=sravn(a.num,b.num);
         int kolvo=(b.num[0]-a.num[0])*4+((c>0)?1:0);
         int buf=a.num[0];
         a.num[0]=0;
         //reply.comma=ceil(kolvo)+3*4;
                reply.comma=3*4+a.comma-b.comma;
         shift (a.num,101-((ceil(kolvo/4))+3+buf),100);
         a.num[0]=buf+(ceil(kolvo/4))+3;
         d_l(a.num,b.num,reply.num);
                if (a.znak+b.znak==1)
                        reply.znak=1;
                else
                        reply.znak=0;

Это сообщение отредактировал(а) Hohhi - 31.3.2008, 10:16

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