Suma lub cyfra kontrolna - cd.

W weryfikacji poprawności numeru konta bankowego systemu IBAN występuje problem dzielenia 18-to cyfrowej liczby całkowitej przez 97. Właściwie chodzi o resztę z dzielenia;

 510007547061111462 MOD 97 = 1  

Uwaga: tak długie liczby całkowite nie dają się przedstawić dokładnie w typowym języku programowania (przepraszam za uproszczenie ;). W trakcie obliczeń należy podzielić długi ciąg cyfr na mniejsze porcje i na nich zrobić obliczenia w trybie tak jak to się robi na papierze. Maksymalna liczba cyfr w podzielonych liczbach zależy od typu całkowitoliczbowego jaki wybierzemy do reprezentacji tych liczb.

Przykład:
  123456789012  dzielimy na dwie liczby:
  123456  i  789012
  123456 MOD 97 = 72  
resztę z dzielenia dopisujemy na początku drugiego kawałka
72789012 MOD 97 = 18  to jest właśnie wynik dzielenia
całkowitego liczby 123456789012 przez 97

Tak więc wystarczyło ciąg cyfr podzielić na dwa kawałki. Ale gdy tych cyfr jest dużo więcej to ciąg cyfr należy podzielić na więcej kawałków. Na ile? To zależy od maksymalnej liczby cyfr w największej liczbie w reprezentacji typu całkowitego jakim się możemy posłużyć w obliczeniach w danym języku programowania.

Dalszą "obróbkę" można zrobić na kilka sposobów. Jeden z czytelników zaroponował procedurę rekurencyjną, a ja zrobiłem to iteracyjnie bo tak mi się wydawało prościej.

Procedura rekurencyjna

Jest takie powiedzenie wśród programistów:
"Iterować jest rzeczą ludzką, wykonywać rekursywnie - boską" ;-)

Poniżej prościutka procedura w Visual Basic.
Sub Modulo( ByRef Wynik As Long, ByVal InNR As String,
            Dv As Long, MaxLen As Variant)
Dim NrVrb As Long

  If Len(InNR) > MaxLen Then
    NrVrb = Val(Left(InNR, MaxLen)) Mod Dv
    InNR = Trim$(Str(NrVrb)) & Right$(InNR, Len(InNR) - MaxLen)
    Modulo Wynik, InNR, Dv, MaxLen
  Else
      Wynik = Val(InNR) Mod Dv
  End If
End Sub

Oczywiście jest tu trochę zbędnych linijek i zmiennych - tylko po to, aby była jasność.

Irek Morawski

Uwaga autora strony: po chwili analizy widać, że procedura się nie sprawdzi w przypadku gdy dzielnik jest długą liczbą, która nie da się przedstawić w danym języku jako liczba dokładna. Ale jest wystarczająca do celu w jakim została napisana. Wszystko zgodnie z chawlebną zasadą programistów - KISS - Keep It Simple Stupid. Procedury, a właściwie, linijki poniżej też pasują do tej zasady i także ich dotyczy powyższe zastrzeżenie.

metoda iteracyjna Turbo Paskal

W internecie zmalazłem takie zdania:
Jeśli dany problem możemy rozwiązać na dwa analogiczne sposoby - jeden rekurencyjnie, a drugi iteracyjnie, to który będzie szybszy? Intuicja mówi, że rekurencja; błąd. O ile metody różnią się tylko sposobem wykonania, a nie całym algorytmem, to wygra iteracja.

Fragmenty programu w Turbo Paskalu v 5.5:
dwie funkcje własne: przeróbki paskalowych procedur na funkcje
- zdefiniowane dla wygody i zwięzłości dalszego programu:
type  Str20 = string[20];

function iStr( iii : longint ): Str20;
var  sss : str20;
begin
     Str( iii, sss );   iStr:=sss
end;

function eVal( sss : Str20 ): longint;
var  iii : longint;   err : integer;
begin
     Val( sss, iii, err );   eVal:= iii
end;

właściwy fragment iteracyjnie obliczający resztę z dzielenia przez 97,
ciąg cyfr jest dany jako łańcuch o nazwie iba
(zmienna napisowa jak kto nie rozumie co to jest łańcuch :)
stała 97 wpisana na twardo do programu,
liczba 6 określa max długość kawałka łańcucha.

     {krok3 reszta z dzielenia przez 97 }
     rrr := 0;     { reszta z dzielenia }
     while (iba > '') do
          begin
               rrr := eVal( iStr(rrr) + Copy(iba,1,6) ) MOD 97;
               iba := Copy(iba,7,255);
          end;
     {krok4 reszta = 1 }
     result := (rrr =1)

A poniżej najprostsze co mogłem wymyśleć

Fragmenty programu w Turbo Paskalu v 5.5:
jedna funkcja własna: przeróbka paskalowej procedury na funkcję
- zdefiniowana dla wygody i zwięzłości dalszego programu:
var i, reszta : integer;
    numer : string;

function eVal( sss : String ): longint;
var  iii : longint;   err : integer;
begin
     Val( sss, iii, err );   eVal:= iii
end;

właściwy fragment iteracyjnie obliczający resztę z dzielenia przez 97,
ciąg cyfr jest dany jako łańcuch o nazwie numer
(zmienna napisowa jak kto nie rozumie co to jest łańcuch :)
stała 97 wpisana na twardo do programu.

begin
     readln( numer );
     {krok3 reszta z dzielenia przez 97 }
     reszta := 0;      for i:=1 to Length(numer) do reszta := (10*reszta + eVal(numer[i])) MOD 97;
writeln( 'Reszta z dzielenia = ', reszta ); readln; end.

metoda iteracyjna - Javascript

   // krok 3 podziel modulo 97; 
   // dana testowa BE62 5100 0754 7061 powinno wyjsc 1
   rr = 0;   L = tempStr.length;
   for ( var i=0; i<L; i=i+6 ) {
   // Uwaga: Netscape i IExpolorer w parseInt 
   //   traktuje 0123 jako zapis oktalny,
   //   wiec lepiej wymusic traktowanie dziesietne
    mod = parseInt(''+mod+tempStr.substring( i, i+6),10 ) % 97;
   }
   // krok 4
   document.forms[0].wynik.value =
                     kopia + ((mod==1)?' =Dobry':' = Zły ');

Program js-pesel napisany w javaskrypcie weryfikuje numer konta bankowego według powyższego algorytmu.

Jeśli nie brać pod uwagę części deklaracyjnych to podejście iteracyjne wydaje się krótsze i prostsze



PS. Gdyby kogoś interesowały inne rozwiązania to radzę
przestudiować stronę w National University of Singapore
     9. Mathematics and Number Theory

albo na Uniwersytecie w Wiedniu
     modulo.cpp,

Linki do bibliotek procedur i opis operacji na wielkich liczbach:
     Ask Dr Math - Arbitrary-Precision Arithmetic

dwie interpretacje operatora modulo dla liczb ujemnych:
     Ask Dr Math - Mod Function and Negative Numbers.

Jest tutaj przykład jak programiści Excela ignorują proste zasady arytmetyki.




ciąg dalszy


          Licznik = (od 28 lipca 2004)
          ostatnie poprawki

Valid HTML 4.01!