; Binary Unsigned Integer Multiplication
; written by Teresa Carrigan, 2004

globals [ start-x praise digits myDigits step multiplicand multiplier product doneyet? ]
breeds [ arrow digit mult prod]
digit-own [ digit-value digit-name ]
mult-own [ digit-value digit-name ]
prod-own [ digit-value digit-name ]
patches-own [ name ]

;  runs setup when program is first loaded
to startup
  setup
end

;  makes the correct number of digits, and the red arrow
;  initializes variables
to setup
  locals [ here-x  n ]
  ca
  set praise [ "You got it!" "Right!" "Correct" "Awesome!" "Perfect!" ]
  set myDigits ["0" "1"]
  set multiplicand ""
  set multiplier ""
  set product ""
    ; random 4 bit multiplier
  repeat 4
    [  set multiplier (word multiplier (random-one-of myDigits)) ]
    ; random 8 bit multiplicand
  repeat 8
    [  set multiplicand (word multiplicand (random-one-of myDigits)) ]
    
  ;  drop leading zeroes
  set multiplicand strip-zero multiplicand
  set multiplier strip-zero multiplier

  repeat length multiplicand    
     [ set product (word product "0") ]
  
;    create header bar at top
    ask patches with [ pycor > 3 ]
      [ set pcolor blue ]
    ask patch-at 6 5
      [ set plabel "Binary Unsigned Integer Multiplication"
        set plabel-color white
        set name -1
      ]
    ask patch-at 6 4
      [ set plabel (word add-commas multiplicand " x " multiplier " = ? ")
        set plabel-color white
        set name -2
      ]

      
;    create explanation bar at the bottom
    ask patches with [ pycor < -3 ]
        [ set pcolor blue ]
    ask patch-at 6 -4
        [ set plabel ""
          set plabel-color white
          set name 1
        ]
    ask patch-at 6 -5
        [ set plabel "" 
          set name 2
        ]
    set step 1
    set doneyet? false
end

to show-again
  ;  drop leading zeroes
  set multiplicand strip-zero multiplicand
  set multiplier strip-zero multiplier
  ask turtles [ die ]
  set product ""
  explain 1 ""
  explain 2 ""  
  set step 1
  set doneyet? false
end

; store in registers, padding with zeroes
to step1
  locals [ here-x pad-to temp-mult ]
  explain 1 "Pad multiplicand with number of digits in multiplier."
  explain 2 "Initialize product to zero."
  set here-x -7
  ask patch-at here-x 3
    [  set plabel "Multiplicand"
       set plabel-color cyan
    ]
  ask patch-at here-x 1
    [  set plabel "Partial Product"
       set plabel-color yellow
    ]
  ask patch-at here-x -1
    [  set plabel ""
       set plabel-color orange
    ]
  
  set pad-to (length multiplier)
  
  repeat pad-to
    [
      set multiplicand (word "0" multiplicand)
      set product (word "0" product)
    ]
  
  set here-x here-x + 1
  set temp-mult multiplicand
  
  repeat length multiplicand  [
     cct-digit 1 [
        set color black
        set label-color cyan
        set label first temp-mult
        set digit-value read-from-string label
        set digit-name "multiplicand"
        setxy here-x 3
      ]
     cct-prod 1 [
        set color black
        set label-color yellow
        set label "0"
        set digit-value 0
        set digit-name "product"
        setxy here-x 1
       ] 
     set temp-mult but-first temp-mult
     set here-x here-x + 1
   ]  ; end repeat 
   
  set step (step + 1)
end

to step2
  locals [ here-x temp-mult ]
  explain 1 "Start with the right-most digit"
  explain 2 "of the multiplier."
  
   set here-x 11
   set temp-mult multiplier
   
   ask patch-at here-x 3
     [ set plabel "Multiplier"
       set plabel-color blue
     ]
     
   repeat length multiplier
     [  
       cct-mult 1 [
          set color black
          set label-color blue
          set label last temp-mult
          set digit-value read-from-string label
          set digit-name "multiplier"
          setxy here-x 2
          ]
       set here-x here-x - 1
       set temp-mult but-last temp-mult
     
     ]
  
  ask max-one-of mult [ xcor ]
    [  set digit-name "current"
       hatch 1 [
             set breed arrow
             set shape "arrow"
             set color blue
             set heading 180
             fd 1
             set heading 90
             fd .4
             set heading 0
             set label ""
         ]
    ]
  set step (step + 1)
end

to step3
  locals [ here-x x ]
  ask mult with [ digit-name = "current" ]
    [  set here-x xcor
       set x digit-value
       set digit-name "done"
       if any? mult-at -1 0
         [ ask mult-at -1 0
             [ set digit-name "current" ]
         ]
    ]
  ifelse x = 0
    [  explain 1 "Current digit is 0.  Don't add."
       explain 2 ""
    ]
    [  explain 1 "Current digit is 1."
       explain 2 "Add multiplicand to partial product."
       do-add
    ]
  set step (step + 1)
end

to do-add
  locals [ here-x carry total this-digit this-prod ]
  ask patches with [ plabel-color = orange ]
    [ set plabel "Adding:" ]
  ask max-one-of digit [ xcor ]
    [ set here-x xcor ]
  set carry 0
  repeat length multiplicand
    [  set this-digit digit-value-of random-one-of digit with [ xcor = here-x ]
       set this-prod digit-value-of random-one-of prod with [ xcor = here-x ]
       set total carry + this-digit + this-prod
       set carry 0
       if total > 1
         [  set total total - 2
            set carry 1
         ]
       cct-prod 1 [
            set color black
            set label-color orange
            set label (word total "")
            set digit-value total
            set digit-name "sum"
            setxy here-x -1
         ]
       set here-x (here-x - 1)
       wait slow-motion * 2
    ]
  ask prod with [ digit-name = "product" ]
         [ die ]
  wait slow-motion
  ask prod
         [  set ycor (ycor + 1)
            wait slow-motion
            set ycor (ycor + 1)
            wait slow-motion
            set label-color yellow
            wait slow-motion
            set digit-name "product"
         ]
  ask patches with [ plabel-color = orange ]
    [ set plabel "" ]
    
end

to step4
  explain 1 "Shift multiplicand left."
  explain 2 ""
  ask min-one-of digit [ xcor ]
    [ die ]
  ask digit
    [ set xcor (xcor - 1) ]
  ask max-one-of digit [ xcor ]
    [  hatch 1
          [
            set breed digit
            set color black
            set label-color cyan
            set label "0"
            set digit-value 0
            set digit-name "multiplicand"
            set xcor (xcor + 1)
            
          ]
    ]
  set step (step + 1)
end

to step5
  explain 1 "Look at next digit."
  ask arrow
    [ set xcor (xcor - 1) ]
  ifelse any? mult with [digit-name = "current" ]
    [  set step 3 ]
    [  set step (step + 1)
       set doneyet? true
    ]
end

to-report strip-zero [ x  ]
  while [ first x = "0" and length x > 1 ]
    [ set x but-first x ]
  report x
end

to step6
  locals [ answer first-num ]
  set answer strip-zero get-number
  set answer add-commas answer 
  set first-num add-commas strip-zero multiplicand
  explain 1 "Finished."
  explain 2 (word first-num " x " multiplier " = " answer)
  ask patches with [ plabel-color = yellow ]
    [ set plabel-color white 
      set plabel "Product"
    ]
  ask prod
    [  set label-color white ]
  set step (step + 1)
end

to explain [ which what ]
  ask patches with [ name = which ]
    [ set plabel what ]
end

;  do whatever step comes next, then wait until user wants to continue
to one-step
  locals [ what-step ]
  set what-step (word "step"  step)
  if step < 7
    [  run what-step  ]
  wait slow-motion
end

;  show all remaining steps
to go
  ifelse step < 7
    [ one-step 
      wait slow-motion
    ]
    [ stop
    ]
end

;  read the digits, storing it as a string
to-report get-number
  locals [ target n num before after k]
  set target ""
  set n (xcor-of max-one-of prod [xcor])
  repeat count prod
    [
      set num label-of random-one-of prod with [ xcor = n ]
      set target (word num target)
      set n (n - 1)
    ]
  set target remove " " target
  report target
end

;  add commas every three digits, so the user won't make copy errors
to-report add-commas [ number ]
  locals [ save k ]
  set save ""
  set k 0
  while [ (length number) > 0 ]
    [
      set save (word last number save )
      set number butlast number
      set k (k + 1)
      if (k = 3) and (length number > 0)
        [ set save (word "," save )
          set k 0
        ]
    ]
  set number save  
  report number
end

;  ask a quiz question - calls ask-mult
to quiz
  locals [save-slow]
  set save-slow slow-motion
  set slow-motion 0
  without-interruption [
    set step 20
    if any? arrow with [ hidden? = false ]
       [ user-message "Clearing previous problem." 
         wait save-slow
       ]
    setup 
    ] 
  wait .5
  ask-mult
  set slow-motion save-slow
end

to ask-mult
  locals [ guess target save-slow]
  set guess user-input  (word "What is the answer to the multiplication problem shown?")
  set guess (word " " guess " ")
  set guess clean-input guess
  while [ step < 7 ]
    [ go ]
  without-interruption [ set target get-number ]
  set guess pad-input guess length target
  ifelse guess = target
    [ user-message random-one-of praise ]
    [ set target add-commas target
      user-message "I'm sorry, but the correct answer is " + target]
end

to-report pad-input [guess number-of-digits]
  while [ length guess < number-of-digits ]
    [ set guess (word "0" guess) ]
  report guess
end

;  cleans up the user input
to-report clean-input [guess]
  locals [ pos k upper lowerList]
  set guess remove " " guess
  set guess remove "," guess
  report guess  
end

; *** NetLogo Model Copyright Notice ***
;
; Copyright 2004 by Teresa W. Carrigan.  All rights reserved.
;
; Permission to use, modify or redistribute this model is hereby granted,
; provided that both of the following requirements are followed:
; a) this copyright notice is included.
; b) this model will not be redistributed for profit without permission
;    from Teresa W. Carrigan.
; Contact Teresa W. Carrigan for appropriate licenses for redistribution 
; for profit.
;
; To refer to this model in academic publications, please use:
; Carrigan, T. (2004).  Binary Unsigned Integer Multiplication model.
; Blackburn College, Carlinville IL.
;
; In other publications, please use:
; Copyright 2004 by Teresa W. Carrigan.  All rights reserved.  
;
; *** End of NetLogo Model Copyright Notice ***
@#$#@#$#@
GRAPHICS-WINDOW
3
10
638
316
12
5
25.0
1
18
1
1
1

CC-WINDOW
414
399
697
773
Command Center

BUTTON
5
321
88
354
NIL
setup
NIL
1
T
OBSERVER
T

SLIDER
435
323
623
356
slow-motion
slow-motion
0
1
0.4
0.1
1
seconds

BUTTON
90
321
172
354
step
one-step
NIL
1
T
OBSERVER
T

BUTTON
174
322
263
355
go
go
T
1
T
OBSERVER
T

BUTTON
266
322
329
355
NIL
quiz
NIL
1
T
OBSERVER
T

BUTTON
332
322
430
355
NIL
show-again
NIL
1
T
OBSERVER
T

@#$#@#$#@
WHAT IS IT?
-----------
This model demonstrates binary unsigned integer multiplication.

HOW IT WORKS
------------
First the model generates two random unsigned binary numbers.  The multiplier will have two to four bits, and the multiplicand will have two to eight bits.  

The multiplicand is padded with leading zeroes (one zero for each bit of the multiplier), and a partial product register is initialized to all zeroes (the same size as the padded multiplicand).  

Each digit of the multiplier is processed, starting with the right-most bit.  If the digit is 0, then the multiplicand is shifted one place to the left, dropping a leading zero and padding with a trailing zero.  If the digit of the multiplier is 1, then the multiplicand is added to the partial product register before being shifted to the left.  
When all the bits in the multiplier are processed, the partial product register will contain the answer to the initial multiplication problem.

HOW TO USE IT
-------------
The setup button generates two random unsigned binary numbers.

The slow-motion slider is an easy way to adjust the speed of the display.  Set it to zero if you want to show the final result as quickly as possible.  0.4 is a good setting for most purposes.

The step button demonstrates the next step, and then stops so you can take notes.  This is useful when you are first learning the method.

The go button does each remaining step, at a speed determined by the slow-motion slider.  This is useful when you do not need to take notes between each step.  If you want to pause the demonstration, click the go button a second time and it will stop after finishing the current step.

The quiz button generates a random multiplication problem and then asks you for the product. 

The show-again button starts the same multiplication problem from the beginning.  This is very useful when your hand-calculations do not agree with the model's calculations.


THINGS TO NOTICE
----------------
This process never does any actual multiplication!  It's all just additions and shifts.

When the multiplier is k bits long, the product will be at most k bits longer than the unpadded multiplicand.

After each time the multiplicand is shifted, there is one additional bit in the partial product register that is never changed (because we just add zero to it).  A faster approach used by many computers is to shift the partial products register right instead of the multiplicand left, with the bits shifted out of the register being stored separately instead of dropped.

THINGS TO TRY
-------------
Set slow-motion to 0.4, click setup, and then click go.

Click setup.  Attempt one step at a time on paper, and then click the step button to check that you did that step correctly.

EXTENDING THE MODEL
-------------------
Allow the user to input the multiplier and multiplicand.

Modify the model to allow larger multipliers.

NETLOGO FEATURES
----------------
Extensive use is made of "other-BREED-here", "min-one-of" and "max-one-of".


RELATED MODELS
--------------
Addition in Other Bases


CREDITS AND REFERENCES
----------------------
This model was written by Teresa W. Carrigan, 2004.  

Permission to use, modify or redistribute this model is hereby granted,
provided that both of the following requirements are followed:
	a) this copyright notice is included.
	b) this model will not be redistributed for profit without permission
	   from Teresa W. Carrigan.
Contact Teresa W. Carrigan for appropriate licenses for redistribution 
for profit.

To refer to this model in academic publications, please use: 
Carrigan, T. (2004). Binary Unsigned Integer Multiplication model.
Blackburn College, Carlinville, IL.

In other publications, please use: 
Copyright 2004 by Teresa W. Carrigan.  All rights reserved.  

FOR MORE INFORMATION
--------------------
For more information on binary unsigned integer multiplication, see:
Null, L. and Lobur, J. "Essentials of Computer Organization and Architecture", First Edition, Jones and Bartlett, pages 54-55.

@#$#@#$#@
default
true
0
Polygon -7566196 true true 150 5 40 250 150 205 260 250

arrow
true
0
Polygon -7566196 true true 150 0 0 150 105 150 105 293 195 293 195 150 300 150

box
true
0
Polygon -7566196 true true 45 255 255 255 255 45 45 45

circle
false
0
Circle -7566196 true true 35 35 230

@#$#@#$#@
NetLogo 2.0.1
@#$#@#$#@
@#$#@#$#@
@#$#@#$#@