|
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
|