NWD dla dużych liczb.

Witam. Mam do napisania program który obliczy nwd z bardzo dużych liczb(do 100 cyfr).Nie mogę użyć funkcji systemowych tylko muszę napisać swoje. Wykombinowałem to tak:

1. Wczytuję liczby z pliku do listboxów( listbox_a- pierwsza liczba, listbox_b - druga liczba).
2. Liczby trzymam w zmiennej string. Czyli w tablicy charów.
   3.Napisałem funkcję która sprawdza czy a>b.
3. Algorytm obliczania Nwd wygląda tak:

while (a<>b) do begin

    if (porownaj(a,b)=True) then
       a:=odejmij(a,b)
    else
       b:=odejmij(b,a);  

5. Teraz potrzebuję funkcję która odejmie od siebie dwie liczby w formacie string w najbardziej wydajny sposób.

Pytania:
a) czy operacje lepiej wykonywać na tablicy charów czy lepiej wprowadzić to do tablicy integer?
b) Jak sprawdzić długość tablicy? Gdy wpiszę setlength(tablica,20) to elementy będą numerowane od 1 do 20?
c) jak prościej napisać ten program?

1. Operuj na 32-bitowych intach. Do takiego możesz włożyć każdą 9 cyfrową liczbę.
2. Odejmuj wielokrotności liczb, np jeśli a jest co najmniej 100x większa od b, to zrób a := odejmij(a, przesunprzecinek(b, 2)), gdzie funkcja przesunprzecinek przesuwa przecinek :P tzn dodaje zera na końcu liczby. Jak sprawdzić szybko ile razy większa jest dana liczba? Po pierwsze porównaj ilość intów które zajmują. Jak już będzie miał ten zgrubny wynik to podziel najbardziej znaczące inty z reprezentacji obu liczb.

Tylko ja mam z góry narzucone że mam użyć funkcji która odejmuje dwie liczby "pisemnie"... i właśnie jej potrzebuję.

No to zrób tak jak napisałem.

Jeśli masz wejściowego stringa: "123456789111222333", to grupując to po 9 cyfr dostaniesz dwa inty: 123456789 i 111222333.

Odejmowanie pisemne jest banalnie proste. Startujesz od ostatnich cyfr - tutaj cyfra to w rzeczywistości 9 cyfr - jeśli odjemna ma mniejszą cyfrę niż odjemnik to robisz przeniesienie, tzn przy klasycznym systemie dziesiętnym (przecinki oddzielają cyfry):

1,5,2 - 6,8 = 1,4,12 - 6,8 = 14,12 - 6,8 = 8,4

Jeśli masz wejściowego stringa: "123456789111222333", to grupując to po 9 cyfr dostaniesz dwa inty: 123456789 i 111222333.

A ja jednak bym proponował robić to na bajtach, bo dużo wolniej nie będzie, a program się uprości zdecydowanie.

Odejmowanie pisemne jest banalnie proste.

No właśnie na bajtach TAK, na intach NIE. Na intach to masa roboty, debuggowania itd. Zwłaszcza że autor tematu nie wygląda na orła w programowaniu.

b) Jak sprawdzić długość tablicy? Gdy wpiszę setlength(tablica,20) to elementy będą numerowane od 1 do 20?
c) jak prościej napisać ten program?

b) length(tablica) , nie będą numerowane od 0..19 jeżeli to array, a 1..20 jeżeli to string (eheh, te niuanse <3 )
c) Na bajtach, ja bym dla jeszcze większego uproszczenia cyfry przerobił na zwykłe chary tzn. '0'=> #0 '1'=>#1 itd. Potem napisać jakąś funkcję odejmującą/porównującą i gotowe... Co prawda nie będzie to rozwiązanie optymalne, ale proste. Widać po twoim algorytmie NWD że na wydajności ci nie zależy.

No to dobra może prościej.
Mam dwie tablicę tab_a i tab_b typu integer. W tablicach mam wpisanę po kolei liczby.
np.
Liczba 13431 to będzie tab_a[0]=1, tab_a[1]=3 itd.

Teraz potrzebuję procedurę lub funkcję która odejmie te dwie liczby(tablice) pisemnie i wynik zapiszę w tablicy a, oczywiście z uwzględnieniem rozmiaru.

Pytanie: Czy jeśli przypiszę tablicę o rozmiarze 5 do tablicy o rozmiarze 6, to czy tablica do której przypisałem zmieni rozmiar na 5?

123:
Operowanie na grupach cyfr raczej nie byłoby dużo trudniejsze. No chyba, że masz jakieś konkretne zastrzeżenia, to napisz, a nie takie ogólnikowe krytyki.

Widać po twoim algorytmie NWD że na wydajności ci nie zależy.

Chcesz, żeby zaimplementował modulo na stringach?

Alternatywą jest też: http://en.wikipedia.org/wiki/Binary_GCD_algorithm Nie trzeba wtedy implementować funkcji przesunprzecinek, ale trzeba zaimplementować funkcję podzielprzezdwa.

Teraz potrzebuję procedurę lub funkcję która odejmie te dwie liczby(tablice) pisemnie i wynik zapiszę w tablicy a, oczywiście z uwzględnieniem rozmiaru.

To ją napisz...?

Pytanie: Czy jeśli przypiszę tablicę o rozmiarze 5 do tablicy o rozmiarze 6, to czy tablica do której przypisałem zmieni rozmiar na 5?

Tak, bo operacje de facto deklaracja tablicy dynamicznej to tylko pointer na realną tablicę (przy czym tablica^ to nie @tablica[0] bo są jeszcze dane do pamiętania rozmiaru, referencji itd.).

Operowanie na grupach cyfr raczej nie byłoby dużo trudniejsze. No chyba, że masz jakieś konkretne zastrzeżenia, to napisz, a nie takie ogólnikowe krytyki.

Jeżeli mamy dwa integery w których jest po 9 cyfr, to żeby znaleźć cyfrę do przeniesienia w dół (przy odejmowaniu) to trzeba przewidzieć możliwości że znajduje się w tym samym incie albo w innym. To taki dosyć mały problem niby, ale nadal mam przeczucie (sic) że będzie sporo trudniej :P .

Chcesz, żeby zaimplementował modulo na stringach?

Właśnie problem w tym, że nawet gdyby odejmowanie byłoby superszybkie to i tak program działałby wolno. Nie mówię jak to ma rozwiązać, po prostu stwierdzam fakt. Więc cała implementacja odejmowania na intach byłaby po nic.

Jeżeli mamy dwa integery w których jest po 9 cyfr, to żeby znaleźć cyfrę do przeniesienia w dół (przy odejmowaniu) to trzeba przewidzieć możliwości że znajduje się w tym samym incie albo w innym. To taki dosyć mały problem niby, ale nadal mam przeczucie (sic) że będzie sporo trudniej .

Ale ja chcę żeby zamienił stringa "123456789" na inta 123456789. I wtedy niech odejmuje całymi intami. Akurat samo odejmowanie nie różni się prawie niczym od implementacji na bajtach. Problemy są raczej przy innych operacjach.

Właśnie problem w tym, że nawet gdyby odejmowanie byłoby superszybkie to i tak program działałby wolno. Nie mówię jak to ma rozwiązać, po prostu stwierdzam fakt. Więc cała implementacja odejmowania na intach byłaby po nic.

Dlatego opisałem mój pomysł odejmowania wielokrotności, aby zbić złożoność. W zasadzie z tym odejmowaniem wielokrotności może mieć złożoność identyczną z algorytmem opartym o dzielenie modulo.

Ale ja chcę żeby zamienił stringa "123456789" na inta 123456789. I wtedy niech odejmuje całymi intami. Akurat samo odejmowanie nie różni się prawie niczym od implementacji na bajtach. Problemy są raczej przy innych operacjach.

No ale mówimy tutaj na operacjach na dużych liczbach czyż nie?

Dlatego opisałem mój pomysł odejmowania wielokrotności, aby zbić złożoność. W zasadzie z tym odejmowaniem wielokrotności może mieć złożoność identyczną z algorytmem opartym o dzielenie modulo.

Może, nie znaczy że będzie mieć...
Daj sobie 99999999999999999999999999999999999999999999999 i 2, zobacz ile będzie liczyć...
To jest bardzo wolny algorytm znajdowania NWD, ja bym od niego zaczął optymalizację.

No ale mówimy tutaj na operacjach na dużych liczbach czyż nie?

Przecież jaką byś sobie bazę nie wybrał, odejmowanie pisemne działa tak samo. Czy to system dwójkowy, trójkowy, dziesiętny, czy, tak jak proponuję, miliardowy. A konwersja między systemem dziesiętnym, a miliardowym jest trywialna - wspomniane przeze mnie grupowanie cyfr.

Może, nie znaczy że będzie mieć...
Daj sobie 99999999999999999999999999999999999999999999999 i 2, zobacz ile będzie liczyć...
To jest bardzo wolny algorytm znajdowania NWD, ja bym od niego zaczął optymalizację.

Ha, no i mój algo tutaj by błyszczał.

a = 999
b = 2
a > b, więc szukamy ile zer można dodać do b, aby dalej było mniejsze od a
t = 200, to b z dodanymi dwoma zerami
a = 799, odjąłem t
a = 599, znowu
a = 399
a = 199
t = 20, teraz trzeba zmniejszyć ilość dodanych zer
a = 179
...
a = 19
t = 2, teraz już nie da się dodać żadnego zera
a = 17
a = 15
...
a = 3
a = 1

W sumie, o ile się nie mylę, 23 odejmowania.

Ponadto, jeżeli:
a = 99999999999999999999999999
b = 2
t = 20000000000000000000000000
To po odjęciu dwójki od pierwszej dziewiątki z a, wiem że nie muszę już dalej odejmować, bo potem są tymczasowo dodane przeze mnie zera. W szczególności - dodawanie tych zer można pominąć i tylko podać parametr do specjalnej funkcji odejmującej.

bismak napisał(a)

No to dobra może prościej.
Mam dwie tablicę tab_a i tab_b typu integer. W tablicach mam wpisanę po kolei liczby.
np.
Liczba 13431 to będzie tab_a[0]=1, tab_a[1]=3 itd.

Teraz potrzebuję procedurę lub funkcję która odejmie te dwie liczby(tablice) pisemnie i wynik zapiszę w tablicy a, oczywiście z uwzględnieniem rozmiaru.

Przede wszystkim przepisując cyfry do tablicy integer'ów odwróć kolejność - niech cyfry mniej znaczące będą przed cyframi bardziej znaczącymi. Obliczając różnicę nie wiadomo ile cyfr będzie miał wynik. Dzięki zmianie kolejności będziesz mógł uciąć (SetLength) te najbardziej znaczące cyfry które już nie są potrzebne, w przeciwnym razie musiałbyś przesuwać wszystkie liczby lub "zapamiętywać" od której komórki tablicy zaczyna się liczba co by skomplikowało tylko kod.

Operuj tylko na dwóch tablicach. Więcej nie potrzebujesz. Odejmując b od a wynik na bieżąco zapisuj w a (i vice-versa).

Odejmowanie zrób podobnie jak na kartce. Różnica będzie taka, że jeśli "braknie" liczby (gdy np. będziesz odejmować cyfrę 5 od cyfry 3) to nie dobieraj sobie z cyfr bardziej znaczących. Zamiast tego zapamiętaj przeniesienie (tak jak przy dodawaniu). Przeniesienie będzie wynosić -10 lub 0 (brakło lub nie brakło).

Zaczynając od cyfr najmniej znaczących, odejmij dwie kolejne cyfry od siebie i do wyniku dodaj przeniesienie (początkowo przeniesienie wynosić będzie 0). Oblicz nowe przeniesienie (-10 jeśli wynik ujemny, 0 gdy wynik nieujemny). Odejmij przeniesienie od wyniku (wynik "zrobi się" nieujemny). Wynik (cyfrę) zapisz w tablicy i przejdź do następnej pary cyfr. I tak aż wyczerpią się cyfry odejmowanej.

Jeśli zostało ci przeniesienie musisz je jeszcze odjąć od wyniku. W tym celu znajdź pierwsze nie-zero w pozostałych cyfrach odjemnej i zmniejsz je o 1.

Licząc kolejne cyfry wyniku zapamiętuj gdzie było ostatnie nie-zero. Cyfra ta będzie najbardziej znaczącą cyfrą wyniku. Pozostałe cyfry w tablicy możesz "uciąć" ustawiając tablicy nową długość. Tu się właśnie przydaje zamiana kolejności cyfr o której pisałem.

Jak już to zrobisz będzie można myśleć o optymalizacji i przyspieszeniu wszystkiego. Pomysł pracy w systemie miliardowym zamiast dziesiętnym jest dobry. O ile złożoność będzie taka sam o tyle czas wykonania za każdym razem będzie kilkukrotnie mniejszy. Jeśli chodzi o wykorzystanie dzielenia modulo to podejrzewam, że operacja dzielenia jest zbyt kosztowna i co najwyżej pogorszymy tylko sprawę.

@Tezcatlipoca:
Chyba gotowca chcą.

Mój stary gotowiec: NWD z bardzo dużych liczb
Ma jakiś błąd, ale nie chciało mi się dochodzić jaki.

adf88 dzięki za dobre rady. Właśnie takiego wyjaśnienia potrzebowałem. Coś nie działa twój sposób albo źle kod napisałem :) ale jutro jeszcze będę kombinował.

Znalazłem jeszcze coś takiego:
http://main.edu.pl/pl/user.phtml?op=lesson&n=32

Napisałem coś takiego:

 unit Unit1; 

{$mode objfpc}{$H+}

interface

uses
  Classes, SysUtils, FileUtil, Forms, Controls, Graphics, Dialogs, StdCtrls;

type

 liczba = record
   tab : array[0..99] of Integer;
   len : Integer;
end;


  { TForm1 }

  TForm1 = class(TForm)
    Button_update: TButton;
    Button_usun: TButton;
    Button_zapisz_plik: TButton;
    Button_wczytaj_plik: TButton;
    Edit_liczba_a: TEdit;
    Edit_liczba_b: TEdit;
    Edit_nazwa_pliku: TEdit;
    Label1: TLabel;
    Label2: TLabel;
    Label3: TLabel;
    Label4: TLabel;
    Label5: TLabel;
    ListBox_liczba_b: TListBox;
    ListBox_nwd: TListBox;
    ListBox_liczba_a: TListBox;
    otworz_plik: TOpenDialog;
    zapisz_plik: TSaveDialog;
    procedure Button_wczytaj_plikClick(Sender: TObject);
    procedure Button_zapisz_plikClick(Sender: TObject);
    procedure oblicz_nwd();
    procedure odejmij(var a,b: liczba);

  private
    { private declarations }
  public
    { public declarations }
  end; 

var
  Form1: TForm1;

  //deklaracja dwoch tablic typu rekordowego
  tab_a:liczba;
  tab_b:liczba;

implementation

{$R *.lfm}

{ TForm1 }

//--------------------------------------Funkcja formatuje tablice na ciag znakow
function formatuj_nwd(var a:liczba):string;
var
  i:integer;
  nwd:string;
begin
      //ustalenie dlugosci
      i:=a.len-1;

      //zapisanie tablicy w zmiennej string
      while (i>=0) do begin
      nwd:=nwd+Inttostr(a.tab[i]);
      Dec(i);
      end;

  //zwrocenie wyniku
  Result:=nwd;

end;
//------------------------------------------------------------------------------




//-----------------------------------------------Procedura wprowadza dane do tablicy
procedure wczytaj_do_tab(a,b:string);
var
  i:integer;
begin

  //ustalanie rozmiaru tablic
  tab_a.len:=Length(a);
  tab_b.len:=Length(b);

 //wczytywanie do tablicy liczby a
 for i:=0 to tab_a.len-1 do
      tab_a.tab[i]:=StrtoInt(a[Length(a)-i]);

 //wczytywanie do tablicy liczby b
 for i:=0 to tab_b.len-1 do
     tab_b.tab[i]:=StrtoInt(b[Length(b)-i]);

end;
//------------------------------------------------------------------------------





//----------------------------------------------funkcja odejmuje dwie liczby pisemnie
procedure TForm1.odejmij(var a,b: liczba);
var
  i,p,dl:integer;
begin

   p:=0;

  //odejmowanie w petli
  for i:=0 to a.len-1 do begin

  if (i<b.len) then
     a.tab[i]:=a.tab[i]-b.tab[i]+p

     else
     a.tab[i]:=a.tab[i]+p;

  if (a.tab[i]<0) then begin

   a.tab[i]:=a.tab[i]+10;
   p:=-1;

   end else
   p:=0;


  end;

   //obcinanie zer jesli zostaly
   while (a.len > 1) and (a.tab[a.len - 1] = 0) do
   Dec(a.len);




end;
//------------------------------------------------------------------------------






//---------------------------------------------------sprawdza czy a jest wiekasz od b
function porownaj():string;
var
  i:integer;
begin

   //jesli dlugosc a jest wieksza to zwraca W
   if (tab_a.len>tab_b.len) then begin
      Result:='W'; Exit;

   //Jesli dlugosc b jest mniejsza to zwraca M
   end else if (tab_b.len>tab_a.len) then begin
      Result:='M'; Exit;

   //przypadek gdy dlugosci sa rowne
   end else begin

   i:=tab_a.len-1;

   while (i>=0) do begin


   //jesli jakis element jest wiekszy to zwraca W
   if (tab_a.tab[i]>tab_b.tab[i]) then begin
      Result:='W'; exit;
   //jesli jakis element jest mniejszy to zwraca M
   end else if (tab_a.tab[i]<tab_b.tab[i]) then begin
       Result:='M'; exit;

   end;
    Dec(i);
   end;

   //jesli wszystkie byly rowne to zwraca R
   Result:='R'; exit;

   end;
end;
//------------------------------------------------------------------------------







//----------------------------------------------------------Funkcja obliczba nwd
procedure TForm1.oblicz_nwd();
begin

   while (porownaj()<>'R') do begin

   if (porownaj()='W') then
       odejmij(tab_a,tab_b)
    else
       odejmij(tab_b,tab_a);

   end;

end;
//------------------------------------------------------------------------------



//-------------------------------------------Zdarzenie gdy klkniemy wczytaj plik
procedure TForm1.Button_wczytaj_plikClick(Sender: TObject);
var
  plik:TextFile;
  liczba,i:integer;
  linia: string;

begin


  //sprawdzanie czy wybrany zostal plik
  if (otworz_plik.Execute=True) then begin

    //skojazenie pliku i otwarcie do zapisu
    AssignFile(plik,otworz_plik.FileName);
    Reset(plik);

    liczba:=1;


    //petla dla wszystkich lini pliku
    while not eof(plik) do begin

    //zczytywanie lini
    ReadLn(plik,linia);

      //sprawdzanie czy linia nie jest pusta
      if (linia<>'') then begin

       //sprawdzanie czy liczba jest parzysta czy niepatrzysta i wpis do odpowiedniego listboxa
       if (liczba mod 2 =1) then
       ListBox_liczba_a.Items.Add(linia)
       else
       ListBox_liczba_b.Items.Add(linia);


      Inc(liczba);

      end;

    end;


  //obliczanie nwd  w petli

  for i:=0 to ListBox_liczba_a.Count-1 do begin

    //wczytywanie liczby do tablic
    wczytaj_do_tab(ListBox_liczba_a.Items[i],ListBox_liczba_b.Items[i]);


    oblicz_nwd();

    ListBox_nwd.Items.Add(formatuj_nwd(tab_a));


  end;


  end;


end;
//------------------------------------------------------------------------------


procedure TForm1.Button_zapisz_plikClick(Sender: TObject);
var
  i:integer;

begin


end;


end.

Teraz chyba będę musiał zastosować przykład wibowita bo dla dużych liczb nie liczy tylko się wiesza. Chyba że mam jakiś błąd?