Текущий архив: 2016.04.17;
Скачать: CL | DM;

Вниз

длинная арифметика деление   Найти похожие ветки 

← →
aka ©   (2015-08-04 19:44) [0]

Все операции получаются без проблем и деление в общем тоже, при условии что делитель не выходит за int64. А как быть если делитель огромный, разбивать делитель наверное нельзя. Можно что-нибудь сделать ?

---

← →
Pavelnk ©   (2015-08-04 20:26) [1]

Я когда то давно возился с действиями со сверх большими числами. Там число вообще рассматривалось как строка и разбивалось на элементы. Есть такой юнит.

---

← →
Kerk ©   (2015-08-04 21:24) [2]

В "Искусстве программирования" Кнута во втором томе есть алгоритм деления длинных чисел.

Ну и готового кода много уже на эту тему.

---

← →
Pavia ©   (2015-08-04 22:03) [3]

Привожу свой текст алгоритм деления. За основу был взят код из книге Окулова  http://comp-science.narod.ru/DL-AR/okulov.htm


function _DivPencilPaper(var Goal, Modular:TLIntBase2; const a, b:TLIntBase2):boolean;
  function FindBin(var Modular:TLIntBase2; const В:TLIntBase2; const ShiftIndex:Integer):Integer;
  var
    Down, Up:Integer;
    C,D:TLIntBase2;
    rs:TRelationship;
  begin
  MyLongInt2VL.Create(C);
  MyLongInt2VL.Create(D);
 Down:=0;
  Up:=ItemBase;
  while Up - 1 > Down Do
   begin
   MyLongInt2VL.Mul(C, В, (Up + Down) div 2);
     MyLongInt2VL._Shl(D,C,ShiftIndex*ItemSize);
     rs:= MyLongInt2VL.Compare(Modular, D);
   case rs of
   rsGreater:
        begin
        Down := (Down + Up) div 2;
        end;
   rsLess:
        begin
        Up := (Up + Down) div 2;
        end;
   rsEquals:
        begin
        Up := (Up + Down) div 2;
        Down := Up
        end;
   end;
    end;
  MyLongInt2VL.Mul(C, B, (Up + Down) div 2);
  rs:= MyLongInt2VL.Compare(Modular, C);
  if rs = rsGreater then
     begin
      MyLongInt2VL._Shl(D,C,ShiftIndex*ItemSize);
      MyLong.Sub(Modular,Modular, D); {находим остаток от деления}
     end else
     begin
      MyLongInt2VL._Shl(D,Modular,ShiftIndex*ItemSize);
      MyLong.Sub(C, C, D);
      MyLongInt2VL.Mov(Modular,C);
     end;
  FindBin := (Up + Down) div 2; {целая часть частного}
  MyLongInt2VL.Destroy(D);
  MyLongInt2VL.Destroy(C);
  end;
var
 A1,B1, Temp:TLIntBase2;
 ShiftIndex:Integer;
 rs:TRelationship;
begin
 MyLongInt2VL.Create(Temp);
 MyLongInt2VL.Create(A1);
 MyLongInt2VL.Create(B1);
 MyLongInt2VL.Mov(A1,A);
 MyLongInt2VL.Neg(A1);
 MyLongInt2VL.Mov(B1,B);
 MyLongInt2VL.Neg(B1);

 Result:=True;

 MyLongInt2VL.Mov(Modular,a1);{первоначальное значение остатка}
ShiftIndex := A1.ItemsCount - B1.ItemsCount;

 MyLongInt2VL._Shl(Temp,B1,ShiftIndex*ItemSize);
 rs:= MyLongInt2VL.Compare(A1, Temp);
If rs = rsLess Then Dec(ShiftIndex);
{B * Osn > A, в результате одна цифра}
MyLongInt2VL.SetLength(Goal, ShiftIndex*ItemSize);
While ShiftIndex >= 0 Do
Begin
 {находим очередную цифру результата}
 Goal.Items[ShiftIndex] := FindBin(Modular, B1, ShiftIndex);
 Dec(ShiftIndex)
End;

 Goal.Sign:=A.Sign*B.Sign;
 TruncLength(Goal);

 MyLongInt2VL.Destroy(B1);
 MyLongInt2VL.Destroy(A1);
 MyLongInt2VL.Destroy(Temp);
end;

function _Div(var Goal:TLIntBase2; const a, b:TLIntBase2):Boolean; overLoad;
var  Modular:TLIntBase2;
begin
MyLongInt2VL.Create(Modular);
result:=True;
 if IsNull(b) then
    begin
    SetInfinity(Goal,A.Sign*B.Sign);
    Result:=False;
    exit;
    end;
 _DivPencilPaper(Goal,Modular,a,b);
end;


>  как быть если делитель огромный, разбивать делитель наверное
> нельзя. Можно что-нибудь сделать ?

Можно. К примеру так делается в gmplib библиотеке.
Подробнее описано в http://domino.mpi-inf.mpg.de/internet/reports.nsf/c125634c000710cd80255ef200387b6e/a8cfefdd1ac031bbc125669b00493127/$FILE/MPI-I-98-1-022.ps

---

← →
Игорь Шевченко ©   (2015-08-04 22:53) [4]

> Привожу свой текст алгоритм деления


Комментарии - друзья программиста.
Имена переменных должны быть осмысленные, это не древний Фортран с ограничением в 6 символов.

---

← →
Pavia ©   (2015-08-04 23:43) [5]

Да комментариев не хватает. Но я привел ссылку на Окулова, где всё прекрасно задокументировано.

1)

> Имена переменных должны быть осмысленные, это не древний
> Фортран с ограничением в 6 символов.

Вы видимо эту фразу у меня же и подсмотрели. Но тут дело другое.
Я для себя уже выработал второе правило.
2) Если было выполнены правильные сокращения. В результате чего получились новые слова со слоговым(звуковым) чтением. И эти сокращения уже обще приняты. То следует использовать их, а не использовать правило 1.
------------
Чем короче слова тем проще их читать. Слово "лазер" Вы же не читаете и не пишете как "усиление света посредством вынужденного излучения".
Так же и тут. Язык живой он развивается и изменяется.

На самом деле я пробовал A,B заменял на делитель и делимое. Но мне не понравилось. Точно также как и Neg, Sub ,Add писал полными словами.

В данном случае алгоритм достаточно трудный и как-то упростить его не получается. Сделать более понятным можно добавив комментарии, вот только проще от этого он не станет.

---

← →
Rouse_ ©   (2015-08-05 02:00) [6]

FGInt обычно решает такие проблемы

---

Страницы: 1 вся ветка

Текущий архив: 2016.04.17;
Скачать: CL | DM;

Наверх

Память: 0.49 MB
Время: 0.003 c