Solved

Algorithm needed to calculate cashier changes..

Posted on 2006-10-31
8
993 Views
Last Modified: 2012-06-27
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
 
0
Comment
Question by:mechanism
  • 4
  • 3
8 Comments
 
LVL 1

Expert Comment

by:mkruisselbrink
ID: 17858654
Your algorithm won't work for all possible coin values, for example if you have three coins, one worth 7, one worth 6 and one worth 1, when asked how many coins should be used to pay 12 cents, your algorithm will return 1 coin of 7 cents and 5 coins of 1 cent, while it is of course possible to pay this with just two coins, both of 6 cents...

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

Author Comment

by:mechanism
ID: 17858723
Hello,
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
0
 
LVL 6

Expert Comment

by:GnarOlak
ID: 17867461
I don't know much about x86 assembly but I can give some ideas about the algorithm.

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.
0
DevOps Toolchain Recommendations

Read this Gartner Research Note and discover how your IT organization can automate and optimize DevOps processes using a toolchain architecture.

 

Author Comment

by:mechanism
ID: 17868038
Your answer is correct. Yes, 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
0
 
LVL 6

Expert Comment

by:GnarOlak
ID: 17868097
I can try but it's been years since I've done anything in assembly.  Wish me luck :)
0
 

Author Comment

by:mechanism
ID: 17868188
Wishing you luck from bottom of my heart (plus crossing fingers..)
:-)

Nick
0
 
LVL 6

Accepted Solution

by:
GnarOlak earned 125 total points
ID: 17868976
OK.  Here's what I did.  I wrote and tested this function in C:

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);-2147483648;2147483647;",128,0,0,0
      .stabs      "char:t(0,2)=r(0,2);0;127;",128,0,0,0
      .stabs      "long int:t(0,3)=r(0,3);-2147483648;2147483647;",128,0,0,0
      .stabs      "unsigned int:t(0,4)=r(0,4);0000000000000;0037777777777;",128,0,0,0
      .stabs      "long unsigned int:t(0,5)=r(0,5);0000000000000;0037777777777;",128,0,0,0
      .stabs      "long long int:t(0,6)=@s64;r(0,6);01000000000000000000000;0777777777777777777777;",128,0,0,0
      .stabs      "long long unsigned int:t(0,7)=@s64;r(0,7);0000000000000;01777777777777777777777;",128,0,0,0
      .stabs      "short int:t(0,8)=@s16;r(0,8);-32768;32767;",128,0,0,0
      .stabs      "short unsigned int:t(0,9)=@s16;r(0,9);0;65535;",128,0,0,0
      .stabs      "signed char:t(0,10)=@s8;r(0,10);-128;127;",128,0,0,0
      .stabs      "unsigned char:t(0,11)=@s8;r(0,11);0;255;",128,0,0,0
      .stabs      "float:t(0,12)=r(0,1);4;0;",128,0,0,0
      .stabs      "double:t(0,13)=r(0,1);8;0;",128,0,0,0
      .stabs      "long double:t(0,14)=r(0,1);12;0;",128,0,0,0
      .stabs      "complex int:t(0,15)=s8real:(0,1),0,32;imag:(0,1),32,32;;",128,0,0,0
      .stabs      "complex float:t(0,16)=R3;8;0;",128,0,0,0
      .stabs      "complex double:t(0,17)=R3;16;0;",128,0,0,0
      .stabs      "complex long double:t(0,18)=R3;24;0;",128,0,0,0
      .stabs      "void:t(0,19)=(0,19)",128,0,0,0
      .stabs      "__builtin_va_list:t(0,20)=*(0,2)",128,0,0,0
      .stabs      "_Bool:t(0,21)=@s8;-16;",128,0,0,0
      .stabs      "func:F(0,19)",36,0,2,_func
      .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,4,-8
      .stabs      "quarters:(0,4)",128,0,4,-12
      .stabs      "dimes:(0,4)",128,0,4,-16
      .stabs      "nickles:(0,4)",128,0,4,-20
      .stabs      "pennies:(0,4)",128,0,4,-24
      .stabs      "interim:(0,4)",128,0,5,-28
      .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:
0
 

Author Comment

by:mechanism
ID: 17869143
Couldn't even wish for something better.
Your help is INVALUABLE.

THANK YOU SO MUCH for your effort.
Going for test immediately (grin)

NICK
0

Featured Post

Netscaler Common Configuration How To guides

If you use NetScaler you will want to see these guides. The NetScaler How To Guides show administrators how to get NetScaler up and configured by providing instructions for common scenarios and some not so common ones.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Best engineering environments for Xilinx Extensible Programming Platform 4 307
Binary Bomb/GDB Questions 10 1,904
Convert dialog units to pixels 5 109
Dialog Button Color 3 114
Does your audience prefer people in photos or no people? How can you best highlight what you’re selling? What are your competitors doing, and what can you do that is different and unique from them?  Continue reading to learn how to make your images …
Google always has something new and amazing up its sleeve, and the most current thing that they have been working on is another step in the evolution of Google Search, from machine learning to its brilliant successor, deep learning.
This tutorial gives a high-level tour of the interface of Marketo (a marketing automation tool to help businesses track and engage prospective customers and drive them to purchase). You will see the main areas including Marketing Activities, Design …
Established in 1997, Technology Architects has become one of the most reputable technology solutions companies in the country. TA have been providing businesses with cost effective state-of-the-art solutions and unparalleled service that is designed…

777 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question