Greatest Common Factor (GCF) Calculator

[Iconoclast]

Alright, I got it working now.

And yet, I have only an hour left. I'll need to take the time to organize and reflect on all this tomorrow. Thank you for your help.

 

[Exophase]

Ah, but each call of the function in recursion gets another copy of the variable(s) so it's a new instance of a and b. Maybe that's where you are getting confused?

You can change the printf("a = %d, b = %d\r\n", a, b); to printf("a (%X) = %d, b(%X) = %d\r\n", &a, a, &b, b); to see that the addresses are different. The compiler may complain or warn about unsigned values for the &a and &b but it should be safe to ignore these.

The addresses might not be different though. The variables a and b are no longer used after gcd is called so the space on the stack frame can be reclaimed. In fact, because gcd is a tail call a sufficiently optimizing compiler can turn the recursive version into something resembling its output for the iterative version.

Iconoclast; A lot of people advocate starting with C++ over C, and I don't disagree with them, but if you can't handle the fundamentals in C then you won't be able to handle them when they're needed in C++, much less the more complex aspects of the language. You'd be well off spending a lot of time with a real C tutorial, because it seems like you're trying to write code without really learning the language and expecting it to just work.

 

[Iconoclast]

I can handle the fundamentals in C++, just not the ones in C. I do not know how to further explain this to everyone; I am uncomfortable with the input and outputting methods. You don't use scanf and printf in C++, so therefore I do not need to understand them to make programs in C++.

In any case, perhaps someday we'll all see.

 

[Cyberman]

Yes the standard C library function of scanf is messy, and will cause all sorts of fun things to happen if you enter the wrong data. Printf however isn't really all that messy and you will find various implementations of sprintf for type std::string floating around because it is actually easier to do formating with than playing with the iostream formating operators (or at the very least less verbose). Printf internally calls vsprintf() which is the variable arguement version of .. sprintf (sprintf calls it as well) the buffer happens to be temporary and the output of printf is directed to stdout (internally).

That being said, I prefer stream IO for files and I've never been thrilled with any of the input format operators used by C or C++. I guess using {}stream and {stream}.read() is my forte' because I often read binary data from a stream.

I've seldom used console IO with C++ because I find it messy for output and input with. Ditto for C for that matter.

Cyb

 

[Exophase]

I can handle the fundamentals in C++, just not the ones in C. I do not know how to further explain this to everyone; I am uncomfortable with the input and outputting methods. You don't use scanf and printf in C++, so therefore I do not need to understand them to make programs in C++.

In any case, perhaps someday we'll all see.

I/O does not constitute the fundamentals of any programming language and are really not what I'm referring to. If you can't figure out how to use printf then there are a lot of other things you'll probably be missing that ARE fundamental to both languages (like the primitive types).

Of course, you can use stdio in C++ too..

But if you want to use C++ and iostream then it doesn't really matter. You're just not going to make it anywhere if you keep trying to code things without first suitably learning the language. Lines like this:

" else if (x != y == 0) {d = x;}
else if (y != x == 0) {d = y;}
else if (y != 0 != x) {d = gcd(x, y);}"

Probably aren't doing anything like what you think they are.

 

[Garstyciuks]

And without iteration or recursion, you can't determine the correct GCF value in a constant time. This has already been pointed out.

 

[mudlord]

To make it easier to understand, I ported Garstyciuks's working C version to Python

The code is:

#Ported to Python by mudlord
#Based on Garstyciuks's C version

def GCF (a ,b):
    while b != 0:
        t = b
        b = a % b
        a = t
    return a

def main():
    a = input ("Number 1")
    b = input ("Number 2")
    print "GCF is:", GCF(a, b)

main()

It uses the same algo as Garstyciuks's.....only real changes are in code clarity, due to Python's dynamic typing, and its using of spaces as a component of syntax.

 

[cooliscool]

And even easier, VB.NET:

Function Declaration:

    Public Function GCF(ByVal a As Integer, ByVal b As Integer) As Integer
        Dim t As Integer
        While b <> 0
            t = b
            b = a Mod b
            a = t
        End While
        Return a
    End Function

Usage:

        Dim r As Integer = 15
        Dim w As Integer = 69
        MsgBox("GCF of " & r & " and " & w & " is: " & GCF(r, w), MsgBoxStyle.Information, "GCF Function")

 

[Exophase]

How is the VB .NET version clearer than the Python version? It's lacking the two (very insignificant in this case) reasons for clarity mudlord mentioned...

For that matter, how is it clearer than the C version? The gcf function is semantically identical, only with different syntax.

 

[Cyberman]

My GCF program this is half C.

This was for a very small system so

//----------------------------------------------------------------------------
// C main line
//----------------------------------------------------------------------------

#include <m8c.h>        // part specific constants and macros
#include "PSoCAPI.h"    // PSoC API definitions for all User Modules

// what is written to this goes to the LCD that simple
struct
{
    BYTE     X, Y;            // set X Y cursor position
    BYTE    Length;            // 0 to 15
    BYTE     Buffer[17];    // ASCIIZ string
} I2CRegs;


BYTE    GreatestCommonFactor(BYTE _A, BYTE _B)
{
    BYTE    Return;
    if(_B > 0)
    {
        Return = GreatestCommonFactor(_B, _A % _B);
    }
    else
    {
        Return = _A;
    }
    return     Return;
}

void main()
{ 
    BYTE    Status;
    // initialize the LCD
    LCD_1_Init();
    // turn the LCD on
    LCD_1_Start();        
    // send something to the LCD
    LCD_1_PrCString("GCF(15,69)");
    // set up I2c Ram Buffer
    BootLdrI2C_1_InitWrite(
        (BYTE *)&I2CRegs,    // Buffer location
        sizeof(I2CRegs)     // read/write section end
        );
    // Enable Global Interrupts
    M8C_EnableGInt;
    // turn on I2C Bus interface
    BootLdrI2C_1_EnableInt();
    // enable I2C slave device
    BootLdrI2C_1_EnableSlave();
    // setup LED output
    LED_1_Start();
    // compute the GCF and put it to the LCD
    Status = GreatestCommonFactor(15, 69);
    // position curser at x = 0 y = 1
    LCD_1_Position(1, 0);
    // print result in hex digits
    LCD_1_PrHexByte(Status);
    // enter actual program loop
    do
    {
        // turn LED off 
        LED_1_Off();
        // Update the status information
        Status = BootLdrI2C_1_bReadI2CStatus();
        // if we have had an update
        if( (Status & I2CHW_ISR_ACTIVE)
            )
        {
            // on during I2s activity
            LED_1_On();
            if(Status & I2CHW_WR_COMPLETE)
            {
                // if we have 3 or more bytes of data in our write data
                LCD_1_Position(0, 0);
                // write the count to the display
                LCD_1_PrHexByte(BootLdrI2C_1_Write_Count);
                // pad the display
                LCD_1_Write_Data(' ');
                // clear the status information
                BootLdrI2C_1_ClrWrStatus();
                // position LCD on next line
                LCD_1_Position(1, 0);
                // print text sent if any
                LCD_1_PrString((BYTE *)&I2CRegs.Buffer);
                BootLdrI2C_1_Write_Count = 0;
            }
        }
        else
        {
            if(Status & (I2CHW_WR_COMPLETE | I2CHW_WR_OVERFLOW))
            {
                BootLdrI2C_1_ClrWrStatus();
                BootLdrI2C_1_Write_Count = 0;    
            }
        }
    }
    while(1 == 1);
}

If you want to see an image of it running click here.

 

[Toasty]

Showoff... :getlost:

 

[Iconoclast]

I/O does not constitute the fundamentals of any programming language and are really not what I'm referring to. If you can't figure out how to use printf then there are a lot of other things you'll probably be missing that ARE fundamental to both languages (like the primitive types).

Of course, you can use stdio in C++ too..

But if you want to use C++ and iostream then it doesn't really matter. You're just not going to make it anywhere if you keep trying to code things without first suitably learning the language. Lines like this:

" else if (x != y == 0) {d = x;}
else if (y != x == 0) {d = y;}
else if (y != 0 != x) {d = gcd(x, y);}"

Probably aren't doing anything like what you think they are.

Yes, I know, the off-topicness, it tingles.

But it is rather unneeded here. I do not mind complaining about my coding, but I just do not give..a fuck about the coding standards. Unless they are for minimal CPU usage or for some valuable reason other than human pickiness. If these equations do not operate exactly as I forsee, then whoever invented C++ sucks at algebra.

If you mean the syntax organizing/curly braces in one line, that is just my general preference and it has not cost me so far and should not. It is easier to read, in single-line block situations.

 

[Garstyciuks]

This isn't off topic. He meant the "x != y == 0" and simillar parts. There's nothing wrong in having { } in one line, you can even omit it, if there's only one line, like d = x;. All sentences in C++ is processed from right to left. So if y is 0, you get x != 1. I can't understand what exact condition you wanted. That line could be interpreted in a number of ways. x != 0 && y == 0, x != y && y == 0, x != 0 && y == 0, and all of these conditions with || instead of &&. I can't imagine how one would understand "x != y == 0" in algebra.

 

[Iconoclast]

This isn't off topic. He meant the "x != y == 0" and simillar parts. There's nothing wrong in having { } in one line, you can even omit it, if there's only one line, like d = x;. All sentences in C++ is processed from right to left. So if y is 0, you get x != 1. I can't understand what exact condition you wanted. That line could be interpreted in a number of ways. x != 0 && y == 0, x != y && y == 0, x != 0 && y == 0, and all of these conditions with || instead of &&. I can't imagine how one would understand "x != y == 0" in algebra.

x != y = 0

y equals 0, but not x. That hard to understand? It's like defining a number as an integer between 1 and 10.

int n;
0 < n < 11

Only this ain't an inequality; it's an equation.

Also, I see system("EXIT"); isn't working as expected....

And yeah, I knew all that && and || stuff; I just preferred using algebra. I know one thing for sure though, I'd rather be skipping on to assembly right now than writing programs in a programming language that does not understand the rules of algebra. Even if saying 2 + 3 = 4 produces an emulator for a platform, not typing it unless accidentally, where I do suck at arithmetic I should add.

But thanks for explaining the skepticism rather than waving it around without explanation like some people. That thing with the curly braces, where you can omit them in single-line instructions, I did not know. An interesting tip...still debating, but I think I'll pass on it.

I have a question now. What if the user enters negative values? The GCF needs to be positive. I know that |x| means the absolute value of x, the distance from 0 on the number line. It forces negative numbers to be positive and leaves positive numbers positive. Useful for squareroots in geometric cases I guess. Now, can this function be used in C++?

EDIT: Or I guess, detect if the number is negative by using the declaration of another variable? Again, I like to avoid declaring new variables.

int gcd, gcd_new, x, y;
[...:  user inputs numbers x and y and program returns gcd]
if (gcd < 0) {gcd_new = gcd * -1;}

 

[Slougi]

There's a great many reasons to bash C and C++, but I don't think the way operators are defined is one of them. The expression

if (x != y == 0) { ... }

has its own meaning in a C-language context. Spelled out in words it means, "If the evaluation x != y results in 0, then ...". There are very few languages that define these operators otherwise.

And yeah, I knew all that && and || stuff; I just preferred using algebra.

The logical operators do more than just that. They are used mainly to control program logic, its flow, not the mathematical aspects. These kinds of operators are universal to all programming languages I know of, and are assumed knowledge for all programmers beyond their first "Hello World!".

Edit: I'm not counting things like brainfuck btw

I have a question now. What if the user enters negative values? The GCF needs to be positive. I know that |x| means the absolute value of x, the distance from 0 on the number line. It forces negative numbers to be positive and leaves positive numbers positive. Useful for squareroots in geometric cases I guess. Now, can this function be used in C++?

EDIT: Or I guess, detect if the number is negative by using the declaration of another variable? Again, I like to avoid declaring new variables.

int gcd, gcd_new, x, y;
[...:  user inputs numbers x and y and program returns gcd]
if (gcd < 0) {gcd_new = gcd * -1;}

There's two ways.

First way:

if (x < 0)
    x = -x;

Second way:

#include <cstdlib>
...
x = std::abs(x);

-slougi

 

[Slougi]

Reading the thread again I have to ask: Iconoclast, do you understand that there is recursion happening in the GCD function? i.e. it is calling itself repeatedly until some end condition is met.

 

[Garstyciuks]

x != y = 0

y equals 0, but not x. That hard to understand? It's like defining a number as an integer between 1 and 10.

int n;
0 < n < 11

Only this ain't an inequality; it's an equation.

I have never seen such definition in algebra as x != y = 0, what I have seen instead is a system, which says that x is not equal to 0 and y is equal to 0.

 

[Iconoclast]

Don't care if you've seen it or not; it's algebra. A system is two or more separate equations, not a statement of equality between three or more terms. The not equal sign (!=) is really an equal sign with a forward slash/solidus (/) through it when written. a = b = c is an algebraic equation. Now, logically....

Yes, I understand that, but to be honest I'm not getting the science of the coding. Why is gcd defined as its own seperate function apart from the main function? If you define gcd as gcd(b, a % b), a) how is that defining the gcd function by using gcd within the gcd function and b) why not just gcd(a, b) if a = a % b; b < a? How is that recursion just using the mod function?

There's a great many reasons to bash C and C++, but I don't think the way operators are defined is one of them. The expression

if (x != y == 0) { ... }

has its own meaning in a C-language context. Spelled out in words it means, "If the evaluation x != y results in 0, then ...". There are very few languages that define these operators otherwise.


The logical operators do more than just that. They are used mainly to control program logic, its flow, not the mathematical aspects. These kinds of operators are universal to all programming languages I know of, and are assumed knowledge for all programmers beyond their first "Hello World!".

Edit: I'm not counting things like brainfuck btw

I know what the friggin' statement means. Now, I must admit, I am not that surprised by the sciences of what is compiled into machine language would contain algebraic sacrifices for humanly interpreted (thus what humans have foolishly designed machines to interpret in compilation at least) logic. I suppose I will have to live with this foolishness, then.

There's two ways.

First way:

if (x < 0)
    x = -x;

Second way:

#include <cstdlib>
...
x = std::abs(x);

-slougi

Don't like that first way; I will still attempt to follow algebraic standards. Of course, in mathematics, if x = -x, then x must be 0. The second way I like better; it mentions the absolute value function directly, although it is merely another example of an algebraically illogical 'reassignment' like the first example.

I must ask, what are the options available in the iostream compilation that are not available in header cstdlib? Let these be just basic functions, for more complex ones I will learn to use cstdlib instead of just iostream alone in future tutorials.

 

[Exophase]

Don't care if you've seen it or not; it's algebra. A system is two or more separate equations, not a statement of equality between three or more terms. The not equal sign (!=) is really an equal sign with a forward slash/solidus (/) through it when written. a = b = c is an algebraic equation. Now, logically....

Imperative programming isn't an algebraic system. Just because the same/similar symbols and/or operators are used in two different contexts doesn't mean that it "logically" follows that they must behave the same in both. It isn't really fair of you to keep saying things like this. Or at the very least, it certainly isn't productive.

Yes, I understand that, but to be honest I'm not getting the science of the coding. Why is gcd defined as its own seperate function apart from the main function?

I don't know what you'd be suggesting on the contrary. Actually, I'd like to know where you're coming from, since you want C to be very mathematically sound I don't understand the mathematical meaning of defining a function "inside" another one (although this is very common in functional programming and indirectly, OOP as well as in other places)

If you define gcd as gcd(b, a % b), a) how is that defining the gcd function by using gcd within the gcd function and b) why not just gcd(a, b) if a = a % b; b < a? How is that recursion just using the mod function?

gcd isn't being defined as JUST gcd(b, a % b), it's being defined as:

gcd(a, 0) = a
gcd(a, b) = gcd(b, a % b)

I don't really understand the conceptual problem with this, recursive definitions are normal in mathematics (not just programming), you should read up more if this isn't clear to you. I wouldn't say something like that if you didn't come off as such a know it all to begin with, of course (even though it's apparent you don't know as much as you want everyone to think)...

I know what the friggin' statement means. Now, I must admit, I am not that surprised by the sciences of what is compiled into machine language would contain algebraic sacrifices for humanly interpreted (thus what humans have foolishly designed machines to interpret in compilation at least) logic. I suppose I will have to live with this foolishness, then.

Yes yes, machine design is foolish because it doesn't fit your half-baked notion of mathematical beauty. You'll never get far in the real world with that attitude, where there are practical concerns with every model and implementation.

Don't like that first way; I will still attempt to follow algebraic standards. Of course, in mathematics, if x = -x, then x must be 0.

That's irrelevant because the C = operator means assignment, not equality (the == operator). If you don't like it you can use a language with different operators, although that's a remarkably petty thing to be so concerned with (then again..)

The second way I like better; it mentions the absolute value function directly, although it is merely another example of an algebraically illogical 'reassignment' like the first example.

You'd be better off using a functional programming language if you're that concerned with such "illogical" things. Unfortunately you won't be able to do many things which make computers interesting devices. Languages like C are imperative. There's a sense of time and state, as in the real world.

I must ask, what are the options available in the iostream compilation that are not available in header cstdlib? Let these be just basic functions, for more complex ones I will learn to use cstdlib instead of just iostream alone in future tutorials.

I really don't understand what you're saying and don't want to risk guessing wrong with you. Try asking in a much more straightforward way.

 

[Iconoclast]

Imperative programming isn't an algebraic system. Just because the same/similar symbols and/or operators are used in two different contexts doesn't mean that it "logically" follows that they must behave the same in both. It isn't really fair of you to keep saying things like this. Or at the very least, it certainly isn't productive.

Neither is complaining and trolling. Nice spelling, though; gotta give you that. You've got some good spelling compared to most people here...Jesus. Not that hard like grammar, which you made a few mistakes in your post of.

I never said anything about the equations behaving the same in both proper algebra and C++; I only said, a = b = c is an equation (not a system of equations), so a != b = c is an algebraic statement as well if a != b is an algebraic statement. Logically.

gcd isn't being defined as JUST gcd(b, a % b), it's being defined as:

gcd(a, 0) = a
gcd(a, b) = gcd(b, a % b)

Yes, I know; a % b = a if b > a. The inclusive first statement doesn't really help much with my point of confusion, but thanks for reminding me I guess.

That's irrelevant because the C = operator means assignment, not equality (the == operator).

Let's not be...too skeptical now.

I knew that since I first tried learning C, but how exactly does that disregard the algebraic laws of the statement?

x = -x
x == -x

Either way, whether equality is checked or not, x must be 0. I may not like monkey math (math that bypasses algebra), but at least I can do the real thing.

Well, you could've fooled me to replying to more components of that post up there, if you didn't give away...too much information.