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

[Papp Zoltán]

2008.09.22. 10:59:37 dátumon Pyrograph Office <office at pyrograph.hu> írta:

> Hello!
>
> Mindenkinek köszönöm az építő jellegű hozzászólásokat, és a jó ötleteket!
>
>> Hát remélem, beválik, kb. 6 órát gyököltem ezen :-)
>
> Zoli, Neked ez megért ennyit? Vagy csupán amolyan "szakmai perverzitás"?
> Azért köszi!
>
> V.

Hali!

Valahol igazad lehet, mindig perverzen szerettem a matekot és az  
algoritmusokat :-), és olyan megérzés szinten motoszkált a fejemben, hogy  
kell lennie egyszerű megoldásnak, és végülis igazam lett. Csak arra  
kellett rájönnöm, hogy 2 osztó (és a két maradéka) összevonható a  
legkisebb közös többszörösévé (és egy új maradékká), innentől kezdve  
mindegy hány osztód van, mert előbb-utóbb elfogynak. És jó az  
algoritmusban az is, hogy sosem léped át számábrázolásilag az eredeti  
osztók legkisebb közös többszörösét, továbbá csak összeadást és kivonást  
igényel.


Alapvetően egyébként a kínai maradéktétel pont a te problémádra adja a  
megoldást, csak az a baj, hogy minden paraméterhez szintén van egy olyan  
feladat benne, ahol egy maradékból és egy osztóból kell megtalálnod egy  
osztandó számot, ami ráadásul egy alapszám egész számú többszöröse. Tehát  
gyakorlatilag számolási igényben majdhogynem visszajutsz az eredeti  
problémához, csak egyszerűbben, elemeire bontva. Ráadásul a szorzások  
közben számábrázolásilag könnyen átlépheted a meglévő határokat, szóval  
mindent összevetve lehet, hogy bonyolultabb (és lassabb) lenne az egész.


Egyébként - ha érdekel - a probléma a következő, ha speciálisan csak a 2  
osztó + 2 maradék összevonásából keletkező új maradékot akarom kiszámolni,  
akkor a kínai maradéktétel megoldása alapján következő az egyszerűsített  
leírás:

Ha d0 és d1 az eredeti osztód, és m0 és m1 a maradék, akkor meg kell  
találnod azt a z0 és z1 egész számokat, melyre teljesül, hogy:

(d1*z0) mod d0 = 1
(d0*z1) mod d1 = 1

Az összevont, új osztó ugye a LKT(d0,d1) lesz (relatív prímek esetén  
d0*d1).

Ekkor az új maradék:
M=(z0*d1*m0+z1*d0*m1) mod LKT(d0,d1)

Szóval bonyásabb, mint egyszerűen ellépegetni, míg egyenlő nem lesz a két  
szám :-) Pláne, hogy a z0 és z1 megkereséséhez megintcsak nincs képlet,  
tehát ott is lépegetni kell, belátható módon szintén max. LKT(d0,d1)-ig.

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