[elektro] Modulo "szorzás"???

[Papp Zoltán]

2008.09.19. 09:49:33 dátumon Pyrograph Office <office at pyrograph.hu> írta:

> Hello, Lista!
>
> Kellene nekem valami nagyon frappáns algoritmus a következőre:
>
> Adott mondjuk 3 paraméter, a következő pozitiv egész értéktartományokkal:
>
> A3 [0..2]
> A5 [0..4]
> A7 [0..6]
>
> Egy konkrét példa a feladatra:
>
> A3 = 2
> A5 = 1
> A7 = 3
>
> A lehető legegyszerübb algoritmust keresném (csak összeadás, kivonás és
> szorzás műveletekből álljon), amivel meg tudnám keresni azt a LEGKISEBB
> pozitiv egész számot (M), amire igaz, hogy a
> 3-mal osztott maradéka 2 (vagyis M mod 3 = 2)
> 5-tel osztott maradéka 1 (vagyis M mod 5 = 1)
> 7-tel osztott maradéka 3 (vagyis M mod 7 = 3)
> (tehát az A3, A5 és A7 jelzik, hogy az M számnak mennyi legyen a maradéka
> 3, 5 és 7-tel való osztáskor)
>
> Jelen példában ugye az M = 101 lenne. De milyen algoritmussal tudnám ezt
> korrektül, paraméterezhetően, gyorsan kiszámolni bármilyen esetre?
>
> Általános (univerzális) algoritmus kellene, mert ez csak egy példa volt,  
> a
> valóságban azonban nem 3 db. paraméter lesz, hanem 8-10 db. (vagy
> mégtöbb), és a paraméterek értékeinek minden lehetséges variációja
> előfordulhat a saját értéktartományukon belül.
>
> Még egy fontos kitétel lenne:
> Ez az algoritmus uC-ben futna; így jó lenne (a fenti példánál maradva) ha
> a számításhoz használt egyik belső változó sem lépné át számítás közben a
> 3*5*7=105 értéket, vagy maximum a 105*7=735 értéket (7 = a legmagasabb
> paraméter a számításban). Ez több paraméternél már lényeges szempont  
> lehet
> azért, hogy ne kelljen a számításhoz szükséges belső változóknak  
> különösen
> hosszabb változótípust létrehozni.
>
> Előre is köszönöm, ha valaki tudna valami egyszerűen nagyszerű és jó
> ötletet adni.
>
> Nyári Viktor
>
> -----------------------------------------
>           elektro[-flame|-etc]

Hali!

Mindent nem fogok matematikailag bebizonyítani, de működik az alábbi cucc:


Az alapja az egésznek, hogy ha N db osztód (d[0]..d[N-1]) és N db  
maradékod (m[0]..m[N-1]) van, akkor igaz az alábbi:

M=x[i]*d[i]+m[i], ahol i=0..N-1, és x[i] természetes szám

M-et keressük.


Ha veszed az első két tagot, és megkeresed azt a legkisebb K számot, amire  
igaz, hogy:

K=x[0]*d[0]+m[0]
K=x[1]*d[1]+m[1]

Ha K létezik, akkor biztos, hogy K<LKT(d[0],d[1])   (LKT: legkisebb közös  
többszörös)
Ha d[0] és d[1] relatív prímek, akkor biztos, hogy K létezik. Ekkor  
LKT(d[0],d[1])=d[0]*d[1]
Ha nem voltak relatív prímek, akkor vagy létezik megoldás, vagy nem. Ekkor  
d[0]*d[1] számpár létezik, de csak LKT(d[0],d[1]) alkalommal van megoldás.  
(pl. ha a két szám 8 és 12, akkor 8*12=96 féle számpár létezik, de ebből  
csak 24 esetben van megoldás, a többinél nem létezik megoldás; pl. nem  
találsz olyan számot, amire K mod 8=1 és K mod 12=2)

A fentiekből adódóan igaz a következő:
M=y*d[0]*d[1]+K, ahol y természetes szám

Ha most elvégzed az alábbi behelyettesítést:
d[0]=LKT(d[0],d[1])
m[0]=K

akkor tovább mehetsz a d[0] és d[2] párokra, majd újra és újra, míg véget  
nem érnek a számok, a végén az m[0]-ban lesz a végeredmény.

K megtalálásához egyszerűen az m[0] és m[1] párokból mindig a kisebbhez  
hozzá kell adni értelemszerűen a d[0] vagy d[1] értékeket, egészen addig,  
míg m[0] egyenlő lesz m[1]-el, vagy az újabb érték túl nem lépi a  
LKT(d[0],d[1])-et.



ALGORITMUS :

Kindulási adatok ('egyenlő' után a kezdeti értékek):

N : ennyi db osztóm van (N>=2)
m[N] : itt vannak a maradékok 0..N-1-ig
d[N] : itt vannak az osztók 0..N-1-ig
i=1 : index
top=LKT(d[0],d[1]) : aktuális legkisebb közös többszöröse d[0] és d[i]-nek


START:
   IF (m[0]==m[i]) THEN GOTO NEXTDIV  //ha egyformák, akkor megvan a  
keresett érték, mehetünk a következőre
   IF (m[0]<m[i]) THEN (m[0]=m[0]+d[0]) ELSE (m[i]=m[i]+d[i]) //a kettő  
közül a kisebbet növeljük az osztójával
   IF ((m[0]>=top) OR (m[i]>=top)) THEN GOTO ERROR //d[i] valamivel nem  
voltak relatív prím -> hiba
   GOTO START //tovább keresünk

NEXTDIV:
   i=i+1 //következő szám jön a sorban
   IF (i==N) THEN GOTO END  //ha ez volt az utolsó -> megvan a keresett  
érték
   //új kezdő értékek beállítása, m[0] már a helyén van
   d[0]=top  // a régi top érték az új osztó
   top=LKT(d[0],d[i]) //új maximum érték
   GOTO START

ERROR:
   // hibakezelés vagy egyszerűen csak:
   RETURN(0)

END:
   RETURN(m[0])


Ha biztos vagy benne, hogy bármely két d[i] érték relatív prím, akkor  
LKT(d[0],d[i]) helyett egyszerűen a d[0]*d[i] képlet használható.


Egyébként az LKT-t a legegyszerűbben az LKO (legnagyobb közös osztó)  
segítségével lehet megtalálni, mert:
LKT(a,b)=a*b/LKO(a,b)

Az LKO(a,b) megtalálása a legegyszerűbben az Eukledeszi-algoritmussal  
lehetséges, azaz:

START:
   IF (a>b) THEN c=a;a=b;b=c;  //mindig legyen 'a' a nagyobb
   WHILE (a>=b) DO a=a-b  //amíg a nagyobb vagy egyenlő b-vel, addig  
kivonjuk az a-ból a b-t
   IF (a<>0) THEN GOTO START //újra kezdjük
   RETURN(b)  //megoldás a b-ben



Egyébként a példád így futna le az algoritmuson:

Ez volt a kiinduló adatod:
A3 = 2
A5 = 1
A7 = 3

Ez behelyettesítve az algoritmusba:
N=3
d[0]=3; m[0]=2
d[1]=5; m[1]=1
d[2]=7; m[2]=3

Az értékek változása sorrendben:
i=1
top=LKT(3,5)=15
//0 és 1 megoldása:
m[0]=2; m[1]=6
m[0]=5; m[1]=6
m[0]=8; m[1]=6
m[0]=8; m[1]=11
m[0]=11; m[1]=11
//új értékek:
i=2
d[0]=15
top=LKT(15,7)=105
//0+1 és 2 megoldása:
m[0]=11; m[2]=10
m[0]=11; m[2]=17
m[0]=26; m[2]=17
m[0]=26; m[2]=24
m[0]=26; m[2]=31
m[0]=41; m[2]=31
m[0]=41; m[2]=38
m[0]=41; m[2]=45
m[0]=56; m[2]=45
m[0]=56; m[2]=52
m[0]=56; m[2]=59
m[0]=71; m[2]=59
m[0]=71; m[2]=66
m[0]=71; m[2]=73
m[0]=86; m[2]=73
m[0]=86; m[2]=80
m[0]=86; m[2]=87
m[0]=101; m[2]=87
m[0]=101; m[2]=94
m[0]=101; m[2]=101

RETURN(101)

Mint a kiskutya, úgy működik! :-) :-D

Megj.: gyorsítani lehet az algoritmust, ha az m[0]=m[0]+d[0] képlet  
helyett m[0]=m[0]+d képletet használod, ahol d=((m[i]-m[0]) DIV d[0])+1.  
Értelemszerűen a fordítottja ugyanez. Ez főleg akkor hatásos, ha d[0] és  
d[i] között már jelentős különbség van. Pl. ha az előző példánál más lenne  
a sorrend, és a d[0]=7,d[1]=5 és d[2]=3 lenne, akkor az első kör után  
d[0]=35 lenne, míg d[2]=3. Ekkor a 101-ig 3-as lépésekben alapvetően menne  
fel a számláló. Az új képlettel fent lenne nemistom 2 vagy 3 lépésben.




Hát remélem, beválik, kb. 6 órát gyököltem ezen :-)


Üdv


-- 
Papp Zoltán
OneWay Electronics Kft
Hangszerviz
szkájpi: oneway[aláhúzás]papp[aláhúzás]zoltan