Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Delphi: Общие вопросы > Остаток от деления


Автор: poisonX 18.2.2006, 11:37
Помогите решить вопрос: необходимо найти остаток от деления очень большого числа на другое не обязательно большое.

Например:

e := 1,00175779247994E3664;
n := 3239;

Необходимо найти: ost := e mod n;

Дело в том, что в памяти e помещается только как тип extended (хотя нет необходимости чтобы оно являлось с плавающей точкой), но операцию mod можно проводить только с целыми числами, а в любое из integer такое число переполняет. Как быть в этом случае?

Автор: Fin 18.2.2006, 11:42
У тебя настолько будет большая целая часть, что я не думаю, что у тебя класическими методами получится выташить остаток от деления. Надо использовать библиотеки поддерживаюшие большие числа.

Автор: poisonX 18.2.2006, 11:49
Как это сделать?

Автор: Fin 18.2.2006, 11:53
Иши библиотеку арифметики большого числа. Или создай ее сам. Просто у тебя число настолько большое, что будет откидываться часть числа при делении. И естественно это будет сказываться на конечном результате.

Автор: poisonX 18.2.2006, 11:59
Да скорее всего никакого результата не будет, т.к при обработки такого числа происходит исключение.

Автор: Guedda 18.2.2006, 12:30
А почитать документацию по модулю Math.pas?
Там очень много всего есть smile

Автор: poisonX 18.2.2006, 12:38
Например?

Автор: Fin 18.2.2006, 12:49
Можно сделать так. Последовательно выбирать целую часть из числа.
1. Все что после Е откладываем пока в сторонку. У нас останется только 1,00175779247994
2. Доводим это число, так чтобы оно было больше 3239 При этом отнимаем разрядность у числа E
10017,5779247994
Е=3664-4=3660
При каждом декременте Е нужно все время проверять, чтобы Е была больше нуля. Как только Е стало равно 0, перейти к шагу 6.
3. Ишем Число которое было бы кратно числу 3239, но приэтом максимально было бы приближено к делимому 3239*3 = 9717
4. Отнимаем от 10017,5779247994 - 9717 = 300,5779247994
5. Переходим к шагу 2 только Теперь для числа полученного в шаге 4
6. конец

Автор: Fin 18.2.2006, 13:12
Я накидал програмку по этому алгоритму на С++. У меня получился ответ 2516. Чуть помудрив с алгоритмом, и перевёл все в целочисленное исчисление получился ответ 1003.

Автор: Guedda 18.2.2006, 13:41
Можешь выложить Сишный код сюда, я посмотрю ??

Автор: Fin 18.2.2006, 13:43
Код

#include <iostream.h>
#include <windows.h>
int main()
{
    DWORD x = 3176;   // 100175779247994 % 3239
    DWORD y = 3239;
    int e=3650;
    while (true)
    {
        while (x<y)
        {
            x *=10;
            e--;
            if (e==0) 
            {
                if (x>y) while (x>y) x -=y;
                cout << x;
                return 0;
            }
        }
        while (x>y) x -=y;

    }


    return 0;
}

Добавлено @ 13:48
Тут остались следы от не целочисленного вычисления smile Не хотел делить лишний раз, чтобы не делать еше больше ошибок при вычислении.
Добавлено @ 13:54
Вот Код почишенный
Код

#include <iostream.h>
int main()
{
    int x =    3176;
    int y = 3239;
    int e=3650;
    while (true)
    {
        while (x<y)
        {
            x *=10;
            e--;
            if (e==0) 
            {
                x %=y;
                cout << x;
                return 0;
            }
        }
        x %=y;

    }


    return 0;
}

Автор: Albinos_x 18.2.2006, 14:27
простенький вариант:
Код
...
uses
  ... , math;
...
// с условием, что значение E+3664; всегда целочисленное 
procedure TForm1.Button1Click(Sender: TObject);
var e:Extended;
    n:Extended;
    ll:integer;
    s,ss:string;
begin
e := 1.00175779247994E+3664;
n := 3239;
s:=floattostr(e);
ss:=floattostr(n);
if pos('E',s)>0 then
   begin
   if pos('E',ss)>0 then
      begin
      ss:=copy(s,pos('E',ss)+1,length(ss));
      ll:=strtoint(ss);
      end
      else
      ll:=length(ss);
    s:=copy(s,pos('E',s)+1,length(s));
    ll:=ll+trunc((strtofloat(s)/(ll-1)-trunc(strtofloat(s)/(ll-1)))*ll);
    ll:=strtoint(s)-ll;
    e:=e*(power(10,-ll));
    end;
while e>n do
   e:=e-n;
Edit1.Text:=floattostr(e);


результат := 3005,779247994

Автор: poisonX 18.2.2006, 15:43
Так, вроде ответ-то должен быть равен 189

Автор: Mayk 18.2.2006, 15:45
1) google говорит, что сущетвуют ExtMod, ExtRem ф-ции в какой-то ESBMaths'е. хмм.
2) В теории может работать вот это
(мы вычитаем делитель из делимого пока можем. Для скорости мы вычитаем не один делитель, а 2**i*делитель, где i мы вначале увеличиваем, а потом уменьшаем )

Код

function fmod(a,b : extended) : extended;
var i : integer;
begin
        i := 1;
        while (a >= b) do begin
                a := a - b;
                b := b * 2;
                i := i + 1;
        end;

        while (i > 1) do begin
                b := b / 2;
                while (a >= b) do 
                        a := a - b;
                i := i - 1;
        end;
        
        fmod := a;
end;

Но на практике - резултат для примера 2838.00.
А вот java'вский big decimal говорит, что результат - 1003.
Нда.

Автор: Albinos_x 18.2.2006, 16:08
виндовский калькулятор говорит
Цитата

2352

Автор: Albinos_x 18.2.2006, 16:25
сейчас попробую опытным путём проверить....

Автор: Mayk 18.2.2006, 16:32
Цитата(Albinos_x @ 18.2.2006, 20:25 Найти цитируемый пост)
сейчас попробую опытным путём проверить....

а подробнее?

зы. ставлю на 1003. уже есть два результат в 1003.

Автор: Albinos_x 18.2.2006, 17:44
Цитата(Mayk @ 18.2.2006, 16:32 Найти цитируемый пост)
а подробнее?

да вот вроде алгоритм ещё один надумал выполняется долго, но зато (вроде) точно можно узнать ответ...
в ручную слишком долго считать...
Добавлено @ 17:46
пока алгорит дошёл до 15 значного числа...

Автор: Albinos_x 18.2.2006, 19:39
первый мой алгорит полностью не верен, т.к. получается что я находил модуль от 100175,779247994 что в корне не верно, тот алгоритм который дошёл до 15 разрядного числа до сих пор считает, поэтому я его немного усовершенствовал.... вот какой получился результат результат:
Цитата

время работы                                              : 54,8290000297129 sec
количество итераций                                  : 85310
модуль числа                                                : 1645
количество изменений коэф. домнажения : 3662


функция:
Код

procedure TForm1.Button1Click(Sender: TObject);
var e,ee:Extended;
    n,nn:Extended;
    ll,li:Extended;
    s:string;
    t:TDateTime;
    I,ii:Int64;
begin
e := 1.00175779247994E+3664;
n := 3239;
ee:=e;
i:=0;ii:=0;
t:=now;
li:=0;
s:=floattostr(ee);
while (ee>(n)) do
   begin
   s:=floattostr(ee);
   if pos('E',s)>0 then
      begin
       s:=copy(s,pos('E',s)+1,length(s));
       ll:=strtofloat(s)-(length(inttostr(trunc(n))));
       end
       else
       begin
       ll:=length(s)-1-(length(inttostr(trunc(n))));
       end;
   if ll>0 then
      nn:=n*(power(10,(ll)))
      else
      nn:=n;
   if li<>ll then ii:=ii+1;
   li:=ll;
   ee:=ee-nn;
   i:=i+1;
   // äîìíàæåíèå íà 10
   Edit2.Text:=floattostr(ll);
   // ïðîìåæóòî÷íûå çíà÷åíèÿ è êîíå÷íîå
   Edit1.Text:=floattostr(ee);
   // èòåðàöèè
   Edit3.Text:=inttostr(i);
   // êîëè÷åñòâî èçìåíåíèé êîýô äîìíàæåíèå íà 10
   Edit5.Text:=inttostr(ii);
   Application.ProcessMessages;
   end;
t:=now-t;
ll:=t/EncodeTime(0,0,1,0);
Edit4.Text:=floattostr(ll)+' sec';
end;

ЗЫ:
Цитата(Mayk @ 18.2.2006, 16:32 Найти цитируемый пост)
зы. ставлю на 1003. уже есть два результат в 1003.

Цитата(Albinos_x @ 18.2.2006, 16:08 Найти цитируемый пост)
виндовский калькулятор говорит

ошибся он тоже говорит 1003...
так что я пока в раздумьях...
ЗЫЫ: Mayk твой алгоритм дает 275....

Автор: Albinos_x 18.2.2006, 20:08
на большёе время работы не обращайте внимания... просто у меня ещё 2 процесса висели, которые процессор под 100 % загрузили...

Автор: Fin 18.2.2006, 20:40
Что то мы совсем забыли школьный курс математики за 2 класс. А в частности деление столбиком smile
Вот программа, которая не просто выдает результат, но и также все число целиком.
Код

#include <iostream.h>

int Num[15]={1,0,0,1,7,5,7,7,9,2,4,7,9,9,4};

int GetNum(int index)
{
 if ((index>=0) && (index<15)) return Num[index];
 else return 0;
}

int main()
{
    int x =    0;
    int y = 3239;
    int fl=0;
    int i=0;
    while (i<=3664)
    {
        if (x<y) 
        {
            x *=10;
            x +=GetNum(i++);
            switch (fl) {
            case 0:
                break;
            case 1:
                fl=2; 
                break;
            case 2:
                cout << '0';
                break;
            }
        }
        else
        {
            fl=1;
            cout << x/y;
            x %=y;
        }

    }
    if (x>y) 
    {
        cout <<x/y;
        x %=y;
    }
    cout << endl << "Ostatok :"<<x <<endl;
    return 0;
}


Это результат, которая выдала программа:
Цитата

30927996062980549552330966347638159925903056498919419573942574868786662550169805
49552330966347638159925903056498919419573942574868786662550169805495523309663476
38159925903056498919419573942574868786662550169805495523309663476381599259030564
98919419573942574868786662550169805495523309663476381599259030564989194195739425
74868786662550169805495523309663476381599259030564989194195739425748687866625501
69805495523309663476381599259030564989194195739425748687866625501698054955233096
63476381599259030564989194195739425748687866625501698054955233096634763815992590
30564989194195739425748687866625501698054955233096634763815992590305649891941957
39425748687866625501698054955233096634763815992590305649891941957394257486878666
25501698054955233096634763815992590305649891941957394257486878666255016980549552
33096634763815992590305649891941957394257486878666255016980549552330966347638159
92590305649891941957394257486878666255016980549552330966347638159925903056498919
41957394257486878666255016980549552330966347638159925903056498919419573942574868
78666255016980549552330966347638159925903056498919419573942574868786662550169805
49552330966347638159925903056498919419573942574868786662550169805495523309663476
38159925903056498919419573942574868786662550169805495523309663476381599259030564
98919419573942574868786662550169805495523309663476381599259030564989194195739425
74868786662550169805495523309663476381599259030564989194195739425748687866625501
69805495523309663476381599259030564989194195739425748687866625501698054955233096
63476381599259030564989194195739425748687866625501698054955233096634763815992590
30564989194195739425748687866625501698054955233096634763815992590305649891941957
39425748687866625501698054955233096634763815992590305649891941957394257486878666
25501698054955233096634763815992590305649891941957394257486878666255016980549552
33096634763815992590305649891941957394257486878666255016980549552330966347638159
92590305649891941957394257486878666255016980549552330966347638159925903056498919
41957394257486878666255016980549552330966347638159925903056498919419573942574868
78666255016980549552330966347638159925903056498919419573942574868786662550169805
49552330966347638159925903056498919419573942574868786662550169805495523309663476
38159925903056498919419573942574868786662550169805495523309663476381599259030564
98919419573942574868786662550169805495523309663476381599259030564989194195739425
74868786662550169805495523309663476381599259030564989194195739425748687866625501
69805495523309663476381599259030564989194195739425748687866625501698054955233096
63476381599259030564989194195739425748687866625501698054955233096634763815992590
30564989194195739425748687866625501698054955233096634763815992590305649891941957
39425748687866625501698054955233096634763815992590305649891941957394257486878666
25501698054955233096634763815992590305649891941957394257486878666255016980549552
33096634763815992590305649891941957394257486878666255016980549552330966347638159
92590305649891941957394257486878666255016980549552330966347638159925903056498919
41957394257486878666255016980549552330966347638159925903056498919419573942574868
78666255016980549552330966347638159925903056498919419573942574868786662550169805
49552330966347638159925903056498919419573942574868786662550169805495523309663476
38159925903056498919419573942574868786662550169805495523309663476381599259030564
98919419573942574868786662550169805495523309663476381599259030564989194195739425
74868786662550169805495523309663476381599259030564989194195739425748687866625501
69805495523309663476381599259030564989194195739425748687866625501698054955233096
6347638159925903056498919419573942574868786662550169805495523
Ostatok :1003
Press any key to continue

Автор: Mayk 18.2.2006, 21:11
Цитата(Albinos_x @ 18.2.2006, 23:39 Найти цитируемый пост)
Mayk твой алгоритм дает 275....

Мы с компиляторами слегка прозевали что исходное число слегка не поместится в extended.
Не паскалевский, не сишный компилеры не заворнингали об этом. smile
Мне потом заместо числа гнус поместил INF. А fmodl от этого безобразия вернула попросту NAN.

Если увеличить точность до сверхточных явовских BigDecimal'ов, то ответ таки получается 1003. Правда пока до него дойдёт... (изначальный делитель в результате был домножен где-то на 2**12160)

Цитата(Albinos_x @ 18.2.2006, 23:39 Найти цитируемый пост)

ошибся он тоже говорит 1003...

ура! 1003 из четырех разных источников.

Думаем ещё.
ps. веселая задачка для субботы

Автор: Fin 18.2.2006, 21:20
Все правильно 1003. Я в своей последней программе одну степень не добирал. Шас там исправлю результат.

Автор: Albinos_x 18.2.2006, 21:25
Цитата(Mayk @ 18.2.2006, 21:11 Найти цитируемый пост)
Думаем ещё.
ps. веселая задачка для субботы

угу...
Цитата(Fin @ 18.2.2006, 20:40 Найти цитируемый пост)
Что то мы совсем забыли школьный курс математики за 2 класс. А в частности деление столбиком

мой последний алгоритм по этому же принципу работает.....

Автор: Fin 18.2.2006, 21:34
Albinos_x, Прогони свой алгоритм на таком числе
Делимое = 1,00175779247994E+14
Делитель = 3239
Результат должен быть
Целая часть = 30927996062
Остаток = 3176

Автор: Albinos_x 18.2.2006, 22:16
Цитата

Целая часть = 30927996062
Остаток = 3176

угу так и получается:
Цитата

время работы                          : 0,0600001774728298 sec
количество итераций                  : 242
модуль числа                          : 3176
количество изменений коэф. домнажения : 12

Автор: Albinos_x 18.2.2006, 22:36
Цитата(Mayk @ 18.2.2006, 21:11 Найти цитируемый пост)
Мы с компиляторами слегка прозевали что исходное число слегка не поместится в extended.

да по идее должно помещаться....
вот что говорит справка делфи:
Цитата

Fundamental real types
Type  Range                                    Significant digits Size in bytes
Extended 3.6 x 10^-4951 .. 1.1 x 10^4932 19-20          10
...
Extendedoffers greater precision than other real types but is less portable. Be careful using Extended if you are creating data files to share across platforms.

Автор: Albinos_x 18.2.2006, 22:54
Цитата(Albinos_x @ 18.2.2006, 22:16 Найти цитируемый пост)
угу так и получается:

по алгоритму Mayk-а тоже этот же результат...

Автор: Fin 19.2.2006, 16:35
Чтобы число 1.00175779247994E+3664 поместилось полностью в память нужно порядка 12172 бита или 1522 байт. Я не думаю, что в java отводят такое количество памяти под одно число. То что они пишут до 4932 степени, естественно идет обрезка большей части числа. Следовательно в данном случае результат подсчета будет не верен.

Автор: Albinos_x 19.2.2006, 21:43
Цитата(Fin @ 19.2.2006, 16:35 Найти цитируемый пост)
Чтобы число 1.00175779247994E+3664 поместилось полностью в память нужно порядка 12172 бита или 1522 байт. Я не думаю, что в java отводят такое количество памяти под одно число. То что они пишут до 4932 степени, естественно идет обрезка большей части числа. Следовательно в данном случае результат подсчета будет не верен.

я тож про это подумал.... вообще у меня есть подозрения, что возможно они используют для этого не те алгоритмы, что тут мы продлогали...

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)