Euclidean Algorithm for Greatest Comon Divisor (GCD)

This board is to show, discuss and archive useful combinator- and logic-creations.
Smart triggering, counters and sensors, useful circuitry, switching as an art :), computers.
Please provide if possible always a blueprint of your creation.
Post Reply
mmmPI
Smart Inserter
Smart Inserter
Posts: 3148
Joined: Mon Jun 20, 2016 6:10 pm
Contact:

Euclidean Algorithm for Greatest Comon Divisor (GCD)

Post by mmmPI »

Source : https://en.wikipedia.org/wiki/Euclidean_algorithm

GCD.jpg
GCD.jpg (108.77 KiB) Viewed 1020 times


Instructions :
Set number A and B in the constant combinators on the left side
Place 1 thing in any of the chest and rotate the inserter so that it transfer the thing.
Read result on the power pole as "B", it is in fact the GCD of the original A and B.

you can change A or B in the constant and rotate the inserter again to update the GCD of the new A and B.
How it works :
The setup with the inserter triggers a pulse for the initial A and B to go into a circuit which is a loop that will yield new A and B every cycle past the initial one. Such circuit is easier to understand when it is not made into a loop, but rather linear, where each "step" of the algorithm is located right next to the other instead of following each other in time. It look like this :
nonlooping.jpg
nonlooping.jpg (198.16 KiB) Viewed 1020 times



The additionnal operation to make it into the first setup was to add a memory cell at the end, that is reset everytime the circuit output a new value, this way it keep the last one before 0, which was the GCD. The memory cell was also made to be reset by the initial pulse from the inserter that feed the initial A and B for ease of use.

The actual code i tried to follow was :

Code: Select all

{
  a = 252;
  b = 105;
  while(b != 0) {
    t = b;
    b = a % b;
    a = t;
  }
  gcd = a;
}
from : https://www.reddit.com/r/factorio/comme ... piler_v01/

because there was no blueprint attached to the video : https://www.youtube.com/watch?v=2Oe_N8yAynY

coppercoil
Filter Inserter
Filter Inserter
Posts: 482
Joined: Tue Jun 26, 2018 10:14 am
Contact:

Re: Euclidean Algorithm for Greatest Comon Divisor (GCD)

Post by coppercoil »

How convenient are setups that deliver results over an undetermined number of tics? I speak not about the detecting that result is ready, but about synchronizing with other data signals that can change over the time. In other words, such function cannot be pipelined (unless linearized).

mmmPI
Smart Inserter
Smart Inserter
Posts: 3148
Joined: Mon Jun 20, 2016 6:10 pm
Contact:

Re: Euclidean Algorithm for Greatest Comon Divisor (GCD)

Post by mmmPI »

coppercoil wrote:
Fri Apr 26, 2024 8:37 am
How convenient are setups that deliver results over an undetermined number of tics? I speak not about the detecting that result is ready, but about synchronizing with other data signals that can change over the time. In other words, such function cannot be pipelined (unless linearized).
I don't know how to rate/rank the convenience. For some use it's ok to have the result and not need to update at a known frequency when you want to math something "once" when the train arrive, or a blueprint that can be expanded by overlap and it would calculate its size at all time it wouldn't need frequent update . I used a square root algo that worked the same way once, but for other use it is problematic i understand.

According to the wikipedia page the number of tics necessary for the algorithm to stop can only be estimated with a upper bound :
The version of the Euclidean algorithm described above—which follows Euclid's original presentation—can take many subtraction steps to find the GCD when one of the given numbers is much bigger than the other. A more efficient version of the algorithm shortcuts these steps, instead replacing the larger of the two numbers by its remainder when divided by the smaller of the two (with this version, the algorithm stops when reaching a zero remainder). With this improvement, the algorithm never requires more steps than five times the number of digits (base 10) of the smaller integer. This was proven by Gabriel Lamé in 1844 (Lamé's Theorem)
The version implemented i found older source in the book from Donald Knuth " The Art of Computer Programming ", it is replacing the larger of the two numbers by its remainder instead of doing subtraction as in the ancient algo if i haven't done mistake in implementation Lamé's theorem should apply so i think=)

I think it also takes roughly 3 tics per step, i haven't got the need to precisely math it out yet, this would mean the result can at most takes 9(digits)*3(tic per digit)*5(step per digit) 145 ticks to be calculated or a few bit more than 2 seconds as order of magnitude. But i'm not sure which number to inputs for this, i haven't managed to find an example that would take long enough for it to be visible at regular speed, it has tendancy to overflow when using larger number, so it probably breaks for any numbers large enough to necessitate maybe 120 ticks ? maybe 100 ticks ? i don't know.

It won't take 10 minutes, it won't get stuck forever but the result doesn't take the same amount of time everytime. It would be possible to "wait" the theorical maximum for small integer everytime, if the GCD is between 2 numbers where the smallest one has say 3 digit max, then the result would take at most 3*3*5 =45 ticks for the computation i think.

I added a part that math out the Lower Common Multiple following those formulas :
gcd.PNG
gcd.PNG (16.12 KiB) Viewed 909 times
inspiration for doing this is from the other thread linked with the blueprint from where i copied the formulas, i'm not sure such implementation is helpful for the problem though :
mmmPI wrote:
Thu Apr 25, 2024 6:24 pm
upper version that overflow more often :


better version, the last of the bottom lane that overflow less often :


I tested quickly the result with online calculator but it is possible i have made a mistake that i didn't see. It wasn't tested for a real purpose i mean.
My plan to use those are a bit different, it is to try and make music :) it would be akin to a "one time calculation" at the beginning, before the song start playing, maybe it would update every minute or so but the timing question would be made into "can it finish in a minute ?" more than "how many ticks required for the correct output to be shown for the first time".

I don't know of other methods that wouldn't work this way for GDC or LCM.

User avatar
Ivelieu
Burner Inserter
Burner Inserter
Posts: 9
Joined: Mon Apr 22, 2024 2:06 am
Contact:

Re: Euclidean Algorithm for Greatest Comon Divisor (GCD)

Post by Ivelieu »

At risk of stating the obvious, if A >= B then neither LCM or GCD will get output. Otherwise, it works great. Very fast and easy to calculate the upper bound to delay reading the output. That factorio circuit compiler looks awesome too, although it seemed to have too many limitations with the flow control. I wonder if there is a way of mapping x86 operations directly to combinators in an efficient way, for example with generated circuits utilising a small inbuilt stack memory and register reads instead of relying entirely on combinator diodes to line up signal delays.

mmmPI
Smart Inserter
Smart Inserter
Posts: 3148
Joined: Mon Jun 20, 2016 6:10 pm
Contact:

Re: Euclidean Algorithm for Greatest Comon Divisor (GCD)

Post by mmmPI »

Ivelieu wrote:
Sat Apr 27, 2024 10:44 am
At risk of stating the obvious, if A >= B then neither LCM or GCD will get output.
That is not the case to me. I'm not sure what happened during your test but i would rather suspect an overflow ?

You can try with A = 125435 and B = 4234, or the reverse and the result are the same to me , and the same as in the online calculator.

Only if A = B it shows nothing. There could be a special derivation to show the number that's just 1 combinator connected to both constant and doing if A=B output A then a wire of the appropriate color to connect the ouput as both LCM and GDC.
Ivelieu wrote:
Sat Apr 27, 2024 10:44 am
I wonder if there is a way of mapping x86 operations directly to combinators in an efficient way, for example with generated circuits utilising a small inbuilt stack memory and register reads instead of relying entirely on combinator diodes to line up signal delays.
I don't know maybe this one : https://github.com/Qon/combinassembly ?

Nidan
Filter Inserter
Filter Inserter
Posts: 254
Joined: Sat Nov 21, 2015 1:40 am
Contact:

Re: Euclidean Algorithm for Greatest Comon Divisor (GCD)

Post by Nidan »

mmmPI wrote:
Sat Apr 27, 2024 3:26 pm
Only if A = B it shows nothing. There could be a special derivation to show the number that's just 1 combinator connected to both constant and doing if A=B output A then a wire of the appropriate color to connect the ouput as both LCM and GDC.
The same seems to happen if A is an exact multiple of B.

And I suggest you think a bit about the purpose of T in the code you posted. Once you realize that, you can cut the calculation part down to two combinators.

Here's a blueprint that includes your version, the two combinator solution, fixes for the A == n * B case and some extra test cases:

mmmPI
Smart Inserter
Smart Inserter
Posts: 3148
Joined: Mon Jun 20, 2016 6:10 pm
Contact:

Re: Euclidean Algorithm for Greatest Comon Divisor (GCD)

Post by mmmPI »

Nidan wrote:
Sat Apr 27, 2024 6:47 pm
mmmPI wrote:
Sat Apr 27, 2024 3:26 pm
Only if A = B it shows nothing. There could be a special derivation to show the number that's just 1 combinator connected to both constant and doing if A=B output A then a wire of the appropriate color to connect the ouput as both LCM and GDC.
The same seems to happen if A is an exact multiple of B.
Haaa that is correct, I was wrong, when A is exact multiple of B or reverse it did also fail. I had not tested enough differents inputs. :cry:
Nidan wrote:
Sat Apr 27, 2024 6:47 pm
And I suggest you think a bit about the purpose of T in the code you posted. Once you realize that, you can cut the calculation part down to two combinators.
The purpose of T was to do like the code i read online x), i thought i could remove the test if B=0 when thinking about it after you mention it but i couldn't reduce it as far as you did without copying x).

I also attempted my own correction for cases where A=B and cases where A=k*B, and added the LCM on top, it's based on the 2 combinators setup for calculations that you showed me, it is using more combinators overall i think, i'm not sure how/why it always works the thing you did.

Instead i used the initial pulse to let A and B through other path initially, so that they would trigger conditions if A=B it would write that value in the memory cell, and won't be overwritten.
It will also try to write the remainder of B%A wich will be the GCD if it's not overwritten by A%B, that seem to solve the problems with the set of input test attached :

A= 120 B=12
A=12 B=120
A=120 B=120
A=252 B=105
A=105 B=252
A= 4181 B=2584
A=28657 B=46368
A=46368 B=75025

The last rows are pairs of successive fibonacci numbers from online generator , because that's the number use in Lamé's theorem, those that will take the most steps. The last 2 pairs are before and after the first to overflow for the LCM, the GCD being 1.
GCD_LCM.jpg
GCD_LCM.jpg (233.08 KiB) Viewed 784 times


Edit: fix input test and edited blueprint

Post Reply

Return to “Combinator Creations”