The CompTIA Cloud+ Basic training course will teach you about cloud concepts and models, data storage, networking, and network infrastructure.

Hello to you all,

The problem is this: I need a small assembly program to calculate cashier's changes R using coins of 50, 20, 10, 5, 2 and 1 cent and only those ones (on any quantity of course). I know from the beginning that 0 < R < 100 and R is integer. Two constraints apply: (a) I shall use the minimum set of coins (i.e. the 50 cent coin is prefered over 2 twenties and 1 ten etc.) and (b) the calculation algorithm should be no more than 6 steps. I have found that the algorithm is

X = R - [(MOD R,Cn)] / Cn

in a loop, where X is each time the amount of coins (in 1st loop are 50s, 2nd loop are 20s etc), R are the changes (i.e. 94 cents etc) and C is the coin used every time (C1 = 50, C2 = 20, C3 = 10 etc) while n is the repetition (1 to 6).

Example: Suppose that changes that should be given are 77 cents and coins are stored in C1, C2 etc.. (C1=50, C2=20, C3=10.. etc).

See the loop:

X1 = [77 - (MOD 77, 50)] / 50 = [77 - 27] / 50 = 50 / 50 = 1 (one coin of 50 cents should be given).

R = R - (X1 * C1) = 77 - (1 * 50) = 27

X2 = [27 - (MOD 27,20)] / 20 = [27 - 7] / 20 = 20 / 20 = 1 (one coin of 20 cents should be given).

R = R - (X2 * C2) = 27 - (1 * 20) = 7

X3 = [7 - (MOD 10, 7)] / 10 = [7 - 7] / 10 = 0 / 10 = 0 (no coins of 10 cents should be given).

R = R - (X3 * C3) = 7 - (0 * 10) = 7

X4 = [7 - (MOD 7, 5)] / 5 = [7 - 2] / 5 = 5 / 5 = 1 (one coin of 5 cents should be given).

R = R - (X4 * C4) = 7 - (1 * 5) = 7 - 5 = 2

etc.

The algorithm is working, but, how do I do this in assembly? And calculation steps to be no more than 6 (the algorithm).

The little program should run on Intel machine. Any help would be appreciated (I use masm but I can use any tool you dictate - THANK you in advance).

Nick

The problem is this: I need a small assembly program to calculate cashier's changes R using coins of 50, 20, 10, 5, 2 and 1 cent and only those ones (on any quantity of course). I know from the beginning that 0 < R < 100 and R is integer. Two constraints apply: (a) I shall use the minimum set of coins (i.e. the 50 cent coin is prefered over 2 twenties and 1 ten etc.) and (b) the calculation algorithm should be no more than 6 steps. I have found that the algorithm is

X = R - [(MOD R,Cn)] / Cn

in a loop, where X is each time the amount of coins (in 1st loop are 50s, 2nd loop are 20s etc), R are the changes (i.e. 94 cents etc) and C is the coin used every time (C1 = 50, C2 = 20, C3 = 10 etc) while n is the repetition (1 to 6).

Example: Suppose that changes that should be given are 77 cents and coins are stored in C1, C2 etc.. (C1=50, C2=20, C3=10.. etc).

See the loop:

X1 = [77 - (MOD 77, 50)] / 50 = [77 - 27] / 50 = 50 / 50 = 1 (one coin of 50 cents should be given).

R = R - (X1 * C1) = 77 - (1 * 50) = 27

X2 = [27 - (MOD 27,20)] / 20 = [27 - 7] / 20 = 20 / 20 = 1 (one coin of 20 cents should be given).

R = R - (X2 * C2) = 27 - (1 * 20) = 7

X3 = [7 - (MOD 10, 7)] / 10 = [7 - 7] / 10 = 0 / 10 = 0 (no coins of 10 cents should be given).

R = R - (X3 * C3) = 7 - (0 * 10) = 7

X4 = [7 - (MOD 7, 5)] / 5 = [7 - 2] / 5 = 5 / 5 = 1 (one coin of 5 cents should be given).

R = R - (X4 * C4) = 7 - (1 * 5) = 7 - 5 = 2

etc.

The algorithm is working, but, how do I do this in assembly? And calculation steps to be no more than 6 (the algorithm).

The little program should run on Intel machine. Any help would be appreciated (I use masm but I can use any tool you dictate - THANK you in advance).

Nick

Also, I don't understand what you mean with "the calculation algorithm should be no more than 6 steps"

THANK you for your comment, this is true, the algorithm has been invented for this particular coin series. Possible other variations will null it, like if you have just one coin of 7 cents, or if you have only 2 coins of 7 and 11 cents (both primes) etc. So, for the time being, please accept the specific batch of coins as standard.

The calculation algorithm should be 6 steps, meaning that when you start to calculate the coins needed for changes up to the moment that you will have the answer in some register, 6 commands will be used. Actually, this is the heart of the problem, since I've found the algorithm.

Nick

1. Divide the change number by 25. The least significant bit will be the number of quarters (0 or 1). Shifted right one bit will be the number of fifty-cent pieces.

2. Multiply the result from step 1 by 25.

3. Subtract the result from 2 from the original value.

4. Divide that by 5. The least significant bit will be the number of nickles (0 or 1). Shifted right one bit will be the number of dimes (0, 1, or 2).

5. Multiply the result from step 4 by 5.

6. Subtract the result from step 5 from the value derived in step 3. That is the number of pennies.

Given 67 cents:

Step 1 gives 2 (10 binary) which is one fifty-cent piece (1x) and zero quarters (0x).

Step 2 gives 50 (2 * 25)

Step 3 gives 17 (67 - 50)

Step 4 gives 3 (011 binary) which is one dime (01x) and one nickle (xx1).

Step 5 gives 15 (3 * 5)

Step 6 gives 2 (17 - 15)

So you need one fifty-cent piece, zero quarters, one dime, one nickle, and two pennies to equal 67 cents.

I am assuming that bit shifting and masking do not count in the limit of 6 math steps.

May I have the source code in assembly please? (I think the points are yours already).

THANK you

NICK

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.

void func(unsigned int change)

{

unsigned int tchange;

unsigned int half_dollars, quarters, dimes, nickles, pennies;

unsigned int interim;

tchange = change;

interim = tchange / 25;

half_dollars = interim & 2;

quarters = interim & 1;

tchange = tchange - interim * 25;

interim = tchange / 5;

dimes = interim & 6;

nickles = interim & 1;

pennies = tchange - interim * 5;

}

I originally had printf statements to test it but took them out. I then compiled it using 'gcc -S -d' to get the assembly code and the debug information. I then inserted the text of the original code where appropriate. Again, I am not well versed in x86 op codes so I won't be of much help interpretting how exactly this code is doing what it does.

This is what it spit out:

.file "func.c"

.stabs "/cygdrive/c/Documents and Settings/MAndrews/My Documents/",100,0,0,Ltext0

.stabs "func.c",100,0,0,Ltext0

.text

Ltext0:

.stabs "gcc2_compiled.",60,0,0,0

.stabs "int:t(0,1)=r(0,1);-214748

.stabs "char:t(0,2)=r(0,2);0;127;

.stabs "long int:t(0,3)=r(0,3);-2147483

.stabs "unsigned int:t(0,4)=r(0,4);00000000

.stabs "long unsigned int:t(0,5)=r(0,5);00000000

.stabs "long long int:t(0,6)=@s64;r(0,6);010

.stabs "long long unsigned int:t(0,7)=@s64;r(0,7);000

.stabs "short int:t(0,8)=@s16;r(0,8);-32

.stabs "short unsigned int:t(0,9)=@s16;r(0,9);0;6

.stabs "signed char:t(0,10)=@s8;r(0,10);-

.stabs "unsigned char:t(0,11)=@s8;r(0,11);0

.stabs "float:t(0,12)=r(0,1);4;0;

.stabs "double:t(0,13)=r(0,1);8;0

.stabs "long double:t(0,14)=r(0,1);12;0

.stabs "complex int:t(0,15)=s8real:(0,1),0

.stabs "complex float:t(0,16)=R3;8;0;",128

.stabs "complex double:t(0,17)=R3;16;0;",1

.stabs "complex long double:t(0,18)=R3;24;0;",1

.stabs "void:t(0,19)=(0,19)",128,

.stabs "__builtin_va_list:t(0,20)

.stabs "_Bool:t(0,21)=@s8;-16;",1

.stabs "func:F(0,19)",36,0,2,_fun

.stabs "change:p(0,4)",160,0,1,8

.globl _func

.def _func; .scl 2; .type 32; .endef

_func:

.stabn 68,0,2,LM1-_func

LM1:

pushl %ebp

movl %esp, %ebp

subl $28, %esp

.stabn 68,0,7,LM2-_func

LM2:

;tchange = change;

movl 8(%ebp), %eax

movl %eax, -4(%ebp)

.stabn 68,0,8,LM3-_func

LM3:

;interim = tchange / 25;

movl -4(%ebp), %edx

movl $1374389535, %eax

mull %edx

movl %edx, %eax

shrl $3, %eax

movl %eax, -28(%ebp)

.stabn 68,0,9,LM4-_func

LM4:

;half_dollars = interim & 2;

movl -28(%ebp), %eax

andl $2, %eax

movl %eax, -8(%ebp)

.stabn 68,0,10,LM5-_func

LM5:

;quarters = interim & 1;

movl -28(%ebp), %eax

andl $1, %eax

movl %eax, -12(%ebp)

.stabn 68,0,11,LM6-_func

LM6:

;tchange = tchange - interim * 25;

movl -28(%ebp), %edx

movl %edx, %eax

sall $2, %eax

addl %edx, %eax

leal 0(,%eax,4), %edx

addl %edx, %eax

leal -4(%ebp), %edx

subl %eax, (%edx)

.stabn 68,0,12,LM7-_func

LM7:

;interim = tchange / 5;

movl -4(%ebp), %edx

movl $-858993459, %eax

mull %edx

movl %edx, %eax

shrl $2, %eax

movl %eax, -28(%ebp)

.stabn 68,0,13,LM8-_func

LM8:

;dimes = interim & 6;

movl -28(%ebp), %eax

andl $6, %eax

movl %eax, -16(%ebp)

.stabn 68,0,14,LM9-_func

LM9:

;nickles = interim & 1;

movl -28(%ebp), %eax

andl $1, %eax

movl %eax, -20(%ebp)

.stabn 68,0,15,LM10-_func

LM10:

;pennies = tchange - interim * 5;

movl -28(%ebp), %edx

movl %edx, %eax

sall $2, %eax

addl %edx, %eax

movl -4(%ebp), %edx

subl %eax, %edx

movl %edx, %eax

movl %eax, -24(%ebp)

.stabn 68,0,16,LM11-_func

LM11:

leave

ret

.stabs "tchange:(0,4)",128,0,3,-4

.stabs "half_dollars:(0,4)",128,0

.stabs "quarters:(0,4)",128,0,4,-

.stabs "dimes:(0,4)",128,0,4,-16

.stabs "nickles:(0,4)",128,0,4,-2

.stabs "pennies:(0,4)",128,0,4,-2

.stabs "interim:(0,4)",128,0,5,-2

.stabn 192,0,0,_func-_func

.stabn 224,0,0,Lscope0-_func

Lscope0:

.stabs "",36,0,0,Lscope0-_func

.text

.stabs "",100,0,0,Letext

Letext: