Lowest Common Denominators

Blitz3D Forums/Blitz3D Beginners Area/Lowest Common Denominators

_PJ_	(Posted 2010) [#1]

I wasn't blew to find this in the code arcs, but I was sure therre was something :S

I need a way to "quickly" calculate the LCD of just two numbers (each number lower than or equal to 2048)

I tried writing my own, but that just lead me to trying to fiddle with the various "Prime Number" calculators, which I also wasn't sure which is the 'best (i.e. quickest)

I can post the code I have if necessary, but if there's a 'complete' solution already available, it will likely be a lot clener than my fudged attempt :)

--edited because my keyboard is dyslexic.

stanrol

(Posted 2010) [#2]

for i=1 to 2048

Floyd

(Posted 2010) [#3]

Someone posted the following binGCD function many years ago. It seems to be about 30% faster than the classic method.

Once you know the greatest common divisor you get the least common multiple by multiplying the numbers, then dividing out the gcd.

To guard against overflow this is done as a*(b/gcd) rather than (a*b)/gcd.
In your case, with small numbers, this doesn't matter.

Here are the LCM and both styles of GCD:

Function LCM( a, b )   ; least common multiple ( denominator )
	Return a * ( b / binGCD( a, b ) )
End Function

;
; Binary GCD Algorithm
;
; Ported from C, original source at:
; <a href="http://remus.rutgers.edu/~rhoads/Code/int_gcd.c" target="_blank">http://remus.rutgers.edu/~rhoads/Code/int_gcd.c</a>
;
; This GCD algorithm is considerably faster than the classic Euclidean version
;
Function BinGCD( a, b )
    Local t = 0
    If a<=0 Then If a = 0 Then Return b: Else a = -a
    If b<=0 Then If b = 0 Then Return a: Else b = -b

    While( Not( ( a Or b )And 1 ) )
        a = a Shr 1
        b = b Shr 1
        t = t + 1
    Wend

    While( Not( a And 1 ) ): a = a Shr 1: Wend
    While( Not( b And 1 ) ): b = b Shr 1: Wend
    
    While a <> b
        If a>b
            a = a - b
            Repeat: a = a Shr 1: Until a And 1
        Else
            b = b - a
            Repeat: b = b Shr 1: Until b And 1
        EndIf
    Wend
    Return a Shl t
End Function

Function gcd( a, b )	; greatest common divisor, traditional algorithm
	If b Return gcd( b, a Mod b ) Else Return a
End Function

xtremegamr

(Posted 2010) [#4]

I'm a bit tired ATM, but my inner programmer is telling me two things:
1) There probably is some code for this in the archives
2) You should probably just brute force it, like stanrol suggested.

This is some code I cobbled together in a few minutes. I'm not 100% sure, but I _THINK_ it works. It didn't get to test is 100%, so use with caution (if at all):

;returns the lcd of the given 2 numbers
Function lcd(num1,num2)

Local x
For x=2 To 2048 ;<-- we start the loop at 2, so that our function doesn't just return 1
	;is this number a multiple of both num1 and num2?
	If IsAMultipleOf(x, num1) And IsAMultipleOf(x, num2) Then
		Return x ;we have found the lcd! WOOT!
	End If
Next

Return 1 ;we didn't find the lcd, so it must be 1

End Function

;returns true if multiple% is a multiple of number%
Function IsAMultipleOf(multiple, number)

If Float( Int(number)/multiple )=Float( Float(number)/multiple ) Then
	Return True
Else
	Return False
End If

End Function

Using the above code, you would find the LCD of 240 and 10 like so:

Print lcd(240,10)

Hope this helps,
xtremegamr

P.S. That IsAMultipleOf() function is a mess. Don't even try to understand it. ;)

Serpent

(Posted 2010) [#5]

I think I have a faster bruteforcing method. I'll post an example soon...

Warpy

(Posted 2010) [#6]

Euclid's algorithm is 2500 years old. Please use that instead of brute-forcing it, or we've all been wasting our time. Copy Floyd's code, it looks good.

Serpent

(Posted 2010) [#7]

BTW xtremegamer, doesn't your function just return the LCF (Lowest Common Factor) of the two numbers? The LCD would be the lowest common multiple of two denominators, so are you effectively asking for a LCM function Malice?

If so, xtremegamer's function needs to have the two variables in IsAMultipleOF() switched around:

...
If IsAMultipleOf(x, num1) And IsAMultipleOf(x, num2) Then
...

xtreme's function should now work as an LCM function rather than an LCF function because IsAMultipleOf checks to see if 'multiple' is a factor of 'number'.

Anyway, here's the fastest thing I can think of for now. Instead of testing all numbers, it only tests multiples of Var1.

Function LCM(Var1, Var2)
	
	Local MyLCM
	MyLCM = Var1
	
	While MyLCM Mod Var2
		
		MyLCM = MyLCM + Var1
		
	Wend
	
	Return MyLCM
	
End Function

BTW, I've used Mod to check for multiples rather than the unrounded float vs. rounded float method (used in IsAMultipleOf() in xtreme's code). On my PC, using Mod is slightly faster.

EDIT: I posted my example as a faster bruteforcing method, but Floyd's method using the binary GCD function is significantly faster than mine :P That would definitely be the best option.

_PJ_	(Posted 2010) [#8]

Oops sorry for the confusion, it was the Lowest Common Factor I wanted, not the lowest common multiple - see what happens when I spend all night coding :D

So extremegamer's function gives the correct result. Is there a more efficient way to get this (LCF)?

Serpent

(Posted 2010) [#9]

It sounds strange that you should need an LCF function rather than an LCM or a HCF, but this should work, and is possibly faster than the original from xtremegamer, and it should work for values > 2048. Don't have time to test it at the moment sorry.

Function lcf(num1,num2)
	
	Local x
	Local y
	y = Sqr#(num1)
	For x=2 To y ;<-- we start the loop at 2, so that our function doesn't just return 1
	;is this number a multiple of num1?
		If IsAMultipleOf(x, num1) Then
			If IsAMultipleOf(num1 / x, num2) Then
				Return num1 / x ; 'num1 / x' is the factor on the other side of num1's square root that corresponds with 'x'
			ElseIf IsAMultipleOf(x, num2) Then
				Return x ;we have found the lcd! WOOT!
			EndIf
		End If
	Next
	
	;Before returning 1, check to see if num1 and num2 are multiples of each other
	;I've put this at the end because the loop will cover the majority of cases
	If IsAMultipleOf(num1, num2) Then
		Return num1
	ElseIf IsAMultipleOf(num2, num1) Then
		Return num2
	EndIf
	Return 1 ;we didn't find the lcf, so it must be 1
	
End Function

;returns true if multiple% is a multiple of number%
Function IsAMultipleOf(multiple, number)

If number Mod multiple Then
	Return False
Else
	Return True
End If

End Function

EDIT: This seems to be 2 to 3 times faster on my PC than the original.
EDIT2: The function has a few mistakes, I'll repost soon...
EDIT3: Corrected function posted.

Kryzon

(Posted 2010) [#10]

Function IsAMultipleOf(multiple, number)

If number Mod multiple Then
Return False
Else
Return True
End If

End Function

Only Sibly can vouch for this, but I think an IF with Else is slower than one without it.
I'd recommend using the following:

Function isAMultipleOf(multiple, number)

	If number Mod multiple Return False
	Return True

End Function

Warner

(Posted 2010) [#11]

I believe that Mod itself is quite slow. That said, the fastest way to do this seems to be avoiding using a function at all. Ie:

If Not(num Mod x)

_PJ_	(Posted 2010) [#12]

It sounds strange that you should need an LCF function rather than an LCM or a HCF

Yep, but I definitely do :) - that's probably why I had so much trouble finding something :D

Thanks very much, Serpent and for the fixes!

Only Sibly can vouch for this, but I think an IF with Else is slower than one without it.

My personal coding habits wouldn't have the redundant Else either, so that's fine. I really don't know about the efficiency there though :)

---edit due to slow typing:
Waner, yueah I agree, calling another function would at least generate more copies of the variables and likely be a tad slower. I'l clwean up what I can from the code posted, but it's grwat I have the method to work from!

Kryzon

(Posted 2010) [#13]

That's even better, Warner :)

Warpy

(Posted 2010) [#14]

Find the GCD of the two numbers, then find the smallest prime which divides that.

Floyd

(Posted 2010) [#15]

At most fourteen primes must be checked. Your program could contain a list of them.

The fifteenth prime is 47, and 2048 < 47*47 so you would never get this far.

Warpy

(Posted 2010) [#16]

Both numbers could be a prime bigger than 47, so if you get to the end of the list then that's the case.

Floyd

(Posted 2010) [#17]

Both numbers could be a prime bigger than 47, so if you get to the end of the list then that's the case.

That's what happens when I don't actually write any code. Of course I was thinking that if d divides n then we just look at the smaller of d and n/d. But that could be 1.

Let's try again with less laziness. We get a little "elbow room" above 2048 for free.

Global prime[13]
For n = 0 To 13 : Read prime[n] : Next		; primes below Sqr( 2209 ).    2209 = 47*47
Data 2,3,5,7,11,13,17,19,23,29,31,37,41,43

Function LCF( a, b )	; Lowest Common Factor. Assumes a,b are in the range 1 to 2208.
	While b
		g = a
		a = b
		b = g Mod b
	Wend
	g = a	; g = greatest common divisor of a and b.

	; Now look for a small prime dividing g...
	For n = 0 To 13
		If (g Mod prime[n]) = 0 Then Return prime[n]
	Next
	Return g	; ...if no small prime is found
End Function

_PJ_	(Posted 2010) [#18]

That's great, Floyd! Thanks