CSC35500 Programming Project 3

 

Problem Statement

You are to write a Linux elf64 assembly language program that performs the following tasks:

1. Prompts the user to enter a positive integer number (of value no more than 264-1.)

2. Prompts the user to enter a second positive integer number (of value no more than 264-1.)

3. Prints out the integer that is the greatest common divisor of the two entered numbers.

 

For those that don’t know, there is a famous algorithm (that is at least 2000 years old) for calculating this value. The greatest common divisor (GCD) algorithm goes as follows:

 

GCD (a, b):

if (b==0)

answer = a else if (a<b)

answer = GCD (b, a) else // (b>=a)

answer = GCD (b, a % b)

 

Some examples:

 

GCD(7, 28)	GCD(28,21)	GCD(234, 432)	GCD(0, 0)
= GCD(28,7)	= GCD(28, 28%21)	= GCD(432, 234)	=0
= GCD(7,28%7)	= GCD(28,7)	= GCD(234, 432%234)
= GCD(7, 0)	= GCD(7, 28%7)	= GCD(234, 198)
=0	= GCD(7,0)	= GCD(198, 234 % 198)
	= 7	= GCD(198,36)
		= GCD(36, 196%36)
		= GCD(36,18)
		= GCD(18, 36%18)
		= GCD(18, 0)
		= 18

 

Note that the algorithm is recursive (which means that recursion was known over 2000 years ago!)

Problem Details

 

• You must write a recursive version of GCD. No exceptions.

• This problem once again requires that you use a Linux machine to complete

• You must use the nasm and ld tools (and likely edb) to complete this project. Other assemblers are not allowed

 

Example Executions

 

The following are several example runs, with program output in normal text and user input in italics. Your program should not attempt to duplicate the formatting - it is provided here to clarify what the input and output of the programs.

 

Enter first number: 7 Enter Second number: 28 The GCD of 7 and 28 is 7.

———————————————————————————————————-

Enter first number:

Enter Second number: 21

The GCD of 28 and 21 is 7.

———————————————————————————————————-

Enter first number:

Enter Second number: 432

The GCD of 234 and 432 is 18.

———————————————————————————————————-

Enter first number: 0 Enter Second number: 0 The GCD of 0 and 0 is 0.

 

Submission

 

You should post to Canvas both your assembly (.s or .asm) source code file(s) and a plain text file (not an MS Word file) called read.me in a zip or tgz file. Make sure the “root” of your submission is a folder (not just a collection of files.)

 

 

The read.me file should contain:

• your name and any other identifying information.

• any special details on how to compile your project

• any special details on how to run your project - note that you cannot circumvent the project specifications here!

• any known bugs your project has, and possible fixes to those bugs (partial credit abounds here).

• an overview of how you solved the project.

• You may put any other information you like in this file, although you are not required to do so - one common additional set of entries is a “software engineering log” that indicates what you have done every time you sat down and worked on the project. Many programmers find that such actually helps you to finish projects faster!