Solving a Single Congruence Equation

[Thomas Klemm]

(07-25-2015 12:54 PM)Bunuel66 Wrote:  I apologize for being too lazy for analyzing the algorithm given in the topic.

No reason to apologize. I should have explained the algorithm or documented the program.
But sometimes I'm too lazy.

Quote:There is another approach using the extended Euclid Algorithm and the Bezout/Merignac theorem but it will be more complex to program. This alternate approach will be the faster at the price of an expense in memory and the use of a structure array like ;-(

Guess what: the extended Euclid Algorithm is used in my program.

(07-25-2015 09:04 PM)Bunuel66 Wrote:  It is mainly a question of what you have in hand. If you are able to compute at least the square of your number without overflow then the modulo operation will limit the expansion at every step
of the loop. It is not that difficult to write algorithms for the 4 elementary operations working on 24 figures if you have operators working on a lower number. It is a bit a brute force solution, but is should work.

For this approach you may have a look at Gerald's post. However I tried to avoid splitting numbers:

Code:

2.    STO ST Y
3.    1E6
4.    MOD
5.    STO ST Z
6.    –

Instead I implemented the multiplication based on addition and made sure that an overflow can't happen:

Code:

65>LBL 00      ; add ( y x -- y+x )
66 RCL 00      ; y x n
67 RCL ST Z    ; y x n y
68 RCL+ ST Z   ; y x n y+x
69 X<Y?        ; no overflow
70 RTN         ; y+x
71 Rv          ; y x n
72 -           ; y x-n
73 +           ; y+x-n
74 END         ; y+x MOD n

You might consider this approach a thought experiment.

If overflow isn't an issue you can resort to the solution in this post.
I assume it's faster than using Eddie's brute force approach but I haven't done any measurements.

Kind regards
Thomas