; Two's Complement Subtraction
; written by Crystal Barchet and Teresa Carrigan, 2004

globals [ start-x save-here-x save-here-y praise digits myDigits column step 
        number-of-digits doneyet? save-A save-B ]
breeds [ arrow negative digit]
arrow-own [ carry state carry-in]
digit-own [ digit-value state]
patches-own [ name ]

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

;  initializes variables
to setup
  locals [ here-x here-y current n]
  ca
  set praise [ "You got it!" "Right!" "Correct" "Awesome!" "Perfect!" "Bravo" "Splendid" ]
  set digits [ "0" "1" ]
  set myDigits digits
  set number-of-digits (2 + random 7)
  set start-x 9
  set here-x start-x - 3
  set here-y 2
  set column here-x
  set doneyet? false
  set current 1
  ;  for each digit
  repeat number-of-digits [
    cct-digit 1
      [
        set color black
        set shape "box"
        set size  2
        setxy here-x here-y
        set digit-value random 2
        if (number-of-digits - current) < 2 and random 100 < 50
          [ set digit-value 0 ]
        set label (item digit-value myDigits) + " "
        set label-color white
        set state "ready"
      ]
    cct-digit 1
      [
        set color yellow
        set shape "bottom"
        set size  2
        setxy here-x (here-y - 2)
        set digit-value random 2
        if (number-of-digits - current) < 3 and random 100 < 50
          [ set digit-value 0 ]
        set label (item digit-value myDigits) + " "
        set label-color white
        set state "B"
      ]
    cct-digit 1
      [
        set size  2
        setxy here-x (here-y - 4)
        set label ""
        set color black
        set label-color cyan
        set state "empty"
        hideturtle
      ]      
     set current (current + 1)
     set here-x (here-x - 1)
  ]
  

  set here-y (here-y - 2)
  set here-x xcor-of min-one-of digit [ xcor ]
  set here-x (here-x - 2)


    
      cct-negative 1 [
      setxy here-x here-y
      set save-here-x here-x 
      set save-here-y here-y 
      set color yellow
      set shape "negative"
      set size .75
    ]

;    create explanation bars at the bottom and top
    ask patches with [ pycor > 3 ]
      [ set pcolor blue ]
    ask patch-at 6 6
      [ set plabel "Two's Complement Subtraction"
        set plabel-color white
        set name -1
      ]
    ask patch-at 6 5
      [ set plabel ""
        set plabel-color white
        set name -2
      ]

    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 0
end



;  add one to the bit pattern (arrow specific procedure)
to increment
  wait slow-motion
  ifelse any? other-digit-here 
    [ ask other-digit-here with [ label > "" ]
      [  ifelse first label = "0"
          [ set label "1 "
            ask arrow [hideturtle]
          ]
          [  set label "0 "
             ask arrow [fd 1 increment]
          ]    ; end ifelse
       ]    ; end ask other-digit-here
     ]    ; end then part of ifelse any?
     [  ask arrow [ hideturtle ]
     ]    ; end ifelse any?
end



 ; return red arrow to starting position
to go-back
  rt 90
  fd 3
  wait slow-motion
  rt 90
  set xcor start-x
  wait slow-motion
  rt 90
  fd 3
  wait slow-motion
  rt 90
  set state "done" 
  hideturtle
end


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

;  pad to eight bits
to step0
  locals [ here-x here-y ]
  set save-A get-number 2
  set save-B get-number 0
  explain  1 "Pad each number to eight bits."
  explain -2 (word "Problem = " save-A " - " save-B)
  set here-x xcor-of min-one-of digit [ xcor ]
  set here-x here-x - 1
  set here-y ycor-of max-one-of digit [ ycor ]
  
  repeat (8 - number-of-digits) [
    wait slow-motion
    ask negative
      [ set heading -90 
        fd 1
      ]
    cct-digit 1
      [
        set color black
        set shape "box"
        set size  2
        setxy here-x here-y
        set digit-value 0
        set label (item digit-value myDigits) + " "
        set label-color white
        set state "ready"
      ]
    cct-digit 1
      [
        set color yellow
        set shape "bottom"
        set size  2
        setxy here-x (here-y - 2)
        set digit-value 0
        set label (item digit-value myDigits) + " "
        set label-color white
        set state "B"
      ]
    cct-digit 1
      [
        set size  2
        setxy here-x (here-y - 4)
        set label ""
        set color black
        set label-color cyan
        set state "empty"
        hideturtle
      ]      
     set here-x (here-x - 1)
  ]

  set step (step + 1)
  
end

;  move B to bottom corner
to step1
   locals [ here-x here-y ]
   explain  1 "A - B = A + (-B)"
   explain  2 "So first calculate -B"
   wait slow-motion
   ask digit with [ state = "B" ]
     [ set heading 180 
       set shape "box"
       set color black
       fd 1
       wait slow-motion
       fd 1
       wait slow-motion
       set heading -90
       repeat 6
         [ fd 1
           wait slow-motion
         ]
     ]
   ask min-one-of digit [ xcor]
     [ set here-x xcor
       set here-y ycor
     ]
   ask patch-at (here-x - 1) here-y
     [ set plabel "B =" 
       set name "B"
     ]
   set step (step + 1)
end

; invert B (change the 1s to 0s and the 0s to 1s)
to step2
  locals [ here-y ]
  ask min-one-of digit [ xcor]
     [ set here-y ycor  ]

  explain 1 "-B = two's complement of B"
  explain 2 "Invert B"
  ;  create red arrow
  cct-arrow 1 [
    set heading -90
    set color red
    set shape "arrow"
    set label-color white
    set carry 0
    setxy start-x here-y 
  ]
 
  ask arrow
  [  
     repeat 17 [
        fd 1
        wait slow-motion
        if any? other-digit-here
          [  flip ]
       ]
       hideturtle
  ]
  ask patches with [ name = "B" ]
    [ set plabel "!B =" ]
  set step (step + 1)
end  

;  add one to inverted B
to step3  
  explain 2 "Add one to inverted B"
  wait slow-motion
  ask arrow [ 
      set xcor 3
      showturtle
      wait slow-motion
      fd 3
      increment 
      hideturtle
    ]
    explain  2 "Finished taking two's complement of B."
    ask patches with [name = "B"]
      [ set plabel "-B =" ]
    set step (step + 1)
    wait slow-motion
end

;  move -B back to start position
to step4
  explain 1 "Now calculate A + (-B)."
  explain 2 ""
  ask patches with [ name = "B" ]
    [ set plabel "" ]
  ask negative
    [ set shape "plus" ] 
   ask digit with [ state = "B" ]
     [ set heading 90
       repeat 6
         [ fd 1
           wait slow-motion
         ]
       set heading 0 
       fd 1
       wait slow-motion
       fd 1
       wait slow-motion
       set shape "bottom"
       set color yellow
       set label-color white
       set state "ready"
     ]
  set step (step + 1)
end


;  add each column of digits
to step5
 locals [ new-digit problem here-x here-y readyList row overflow? ]
 set readyList (digit with [ state = "ready" ])
 ifelse count readyList > 0
  [ set column xcor-of max-one-of readyList [ xcor ]
   ask arrow [
     explain 2 "Carry-in = " + carry
     set carry-in carry
     setxy column 3
     set heading 180
     showturtle 
     wait slow-motion
     if carry > 0
       [ wait slow-motion ]
     ;set base save-base
     fd 1
     wait slow-motion
     ;  top digit this column
     ask other-digit-here 
         [ set new-digit label 
           set state "done"
         ]
     set new-digit remove " " new-digit
     set new-digit position new-digit myDigits
     explain 2 (word carry  " + " new-digit  " + ?")
     set problem new-digit 
     fd 1
     wait slow-motion
     fd 1
     wait slow-motion
     ;  second digit this column
     ask other-digit-here 
         [ set new-digit label 
           set state "done"
         ]
     set new-digit remove " " new-digit
     set new-digit position new-digit myDigits
     explain 2 (word carry " + " problem " + " new-digit)
     set problem (problem + new-digit + carry)
     set carry 0
     fd 1
     wait slow-motion
     fd 1
     ;  calculate sum and carry
     set label ""

     if problem >= 2
         [ explain 2 (word problem " >= 2, so subtract 2")
           wait slow-motion
           set problem problem - 2
           set carry 1 
         ]
     ask other-digit-here 
         [
             set label (item problem myDigits) + " "
             set state "done"
             showturtle
         ]
     if carry > 0
       [  set label (word carry " ")  ]
     fd 1
     wait slow-motion
     ifelse problem < 10
       [  explain 2 (word "Carry = " carry "; Sum = " problem)  ]
       [  explain 2 (word "Carry = " carry "; Sum = " problem " = " (item problem digits))  ]
     fd 1
     set new-digit carry
      ]

  ]
  [ ; finished all columns
    set step step + 1
    wait slow-motion
    set doneyet? true
    ask arrow
      [
        ifelse carry = carry-in
          [ set overflow? false]
          [ set overflow? true ]
        setxy (xcor - 1) 3
        set state "resting"
      ]
    ifelse overflow?
      [
        explain 2 (word "Carry-in != Carry-out: Overflow.")
        ask patch-at -2 -2
          [ set plabel "Overflow ERROR "
            set plabel-color red
          ]

        ask min-one-of digit [ ycor ]
          [ set row ycor]
        ask digit with [ ycor = row ]
          [ set label-color red ]
      ]
      [
        explain 2 (word "No overflow.")
        ask patch-at -2 -2
          [  set plabel "Answer  "
             set plabel-color cyan
          ]

      ]
  ]
end



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

;  pad user input to 8 bits
to-report pad-input [guess]
  while [ length guess < 8 ]
    [ set guess (word "0" guess) ]
  report guess
end

;  cleans up the user input
to-report clean-input [guess]
  set guess remove " " guess
  set guess remove "," guess
  report pad-input guess  
end

;  read the digits of the answer, storing it as a string
to-report get-number [ y ]
  locals [ target row answerList current]
  set target ""
  set answerList digit with [ ycor = y ]
  while [ count answerList > 0 ]
  [  set current min-one-of answerList [ xcor ]
     set target (word target label-of current)
     set answerList answerList with [ xcor > (xcor-of current) ]
  ]

  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



; flips the digits (called by the invert procedure)
to flip
  if any? other-digit-here
    [
      ask other-digit-here with [ label > ""]
        [  set label-color yellow
           
            ifelse first label = "0"
              [  set label "1 "]
              [  set label "0 "]
        ]
    ]
end



; adds a space in the number so it can be read easier
to-report add-space [ target ]
  locals [ before after result k ]
  set k length target
  ifelse k > 4
    [  set before substring target 0 4
       set after substring target 4 k
       set result (word before " " after)
    ]
    [  set result target ]
  report result
end



; creates a random quiz quesiton and praise if it is right and says its wrong if it is
to ask-question
  locals [ guess save-slow target]
  set guess user-input (word "What is the answer to the problem shown?")
  set guess (word " " guess " " )
  set guess clean-input guess
  set save-slow slow-motion
  set slow-motion 0
  while [ step < 6 ]
    [  go ]
  set slow-motion save-slow
  without-interruption [ set target get-number -2]
  ifelse
  guess = target
    [  user-message random-one-of praise ]
    [  user-message "I'm sorry, but the correct answer is " + target ]
end



to quiz
  locals [qt flag]
  set flag true
  ask arrow 
    [ ifelse (state = "resting") or (hidden? = true)
        [ set flag true ]
        [ set flag false  ]
    ]
  ifelse flag
   [  without-interruption [setup ] 
      wait .5
      ask-question
   ]
   [
       user-message "No quiz until arrow finishes."
   ]
end


; this is the go button, that when pressed, goes through the entire simulation
to go
  ifelse  step < 6 
    [  one-step
       wait slow-motion
    ]
    [  stop
    ]
end

to show-again
  locals [ here-x here-y current n string-A string-B]
  set start-x 9
  set here-x start-x - 3
  set here-y 2
  set column here-x
  set doneyet? false
  set current 1
  set string-A save-A
  set string-B save-B

  ask turtles [ die ]
  ask patches [ set plabel "" ]

  ;  for each digit
  repeat number-of-digits [
    cct-digit 1
      [
        set color black
        set shape "box"
        set size  2
        setxy here-x here-y
        set digit-value read-from-string last string-A
        set string-A but-last string-A
        set label (item digit-value myDigits) + " "
        set label-color white
        set state "ready"
      ]
    cct-digit 1
      [
        set color yellow
        set shape "bottom"
        set size  2
        setxy here-x (here-y - 2)
        set digit-value read-from-string last string-B
        set string-B but-last string-B
        set label (item digit-value myDigits) + " "
        set label-color white
        set state "B"
      ]
    cct-digit 1
      [
        set size  2
        setxy here-x (here-y - 4)
        set label ""
        set color black
        set label-color cyan
        set state "empty"
        hideturtle
      ]      
     set current (current + 1)
     set here-x (here-x - 1)
  ]
  

  set here-y (here-y - 2)
  set here-x xcor-of min-one-of digit [ xcor ]
  set here-x (here-x - 2)


    
      cct-negative 1 [
      setxy here-x here-y
      set save-here-x here-x 
      set save-here-y here-y 
      set color yellow
      set shape "negative"
      set size .75
    ]

  explain -1 "Two's Complement Subtraction"
  explain -2 ""
  explain 1 ""
  explain 2 ""

  set step 0
end

; *** NetLogo Model Copyright Notice ***
;
; Copyright 2004 by Crystal R. Barchet and Teresa 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 Carrigan.
; Contact Teresa Carrigan for appropriate licenses for redistribution 
; for profit.
;
; To refer to this model in academic publications, please use:
; Barchet, C. and Carrigan, T. (2004).  Two's Complement Subtraction model.
; Blackburn College, Carlinville, IL.
;
; In other publications, please use:
; Copyright 2004 by Crystal R. Barchet and Teresa W. Carrigan.  All rights reserved.  
;
; *** End of NetLogo Model Copyright Notice ***
@#$#@#$#@
GRAPHICS-WINDOW
3
10
488
366
9
6
25.0
1
22
1
1
1

CC-WINDOW
79
451
291
512
Command Center

BUTTON
3
367
78
400
NIL
setup
NIL
1
T
OBSERVER
T

BUTTON
79
368
152
401
step
one-step
NIL
1
T
OBSERVER
T

BUTTON
153
368
226
401
go
go
T
1
T
OBSERVER
T

SLIDER
3
402
191
435
slow-motion
slow-motion
0
1
0.15
0.05
1
seconds

BUTTON
227
368
299
401
quiz
quiz
NIL
1
T
OBSERVER
T

BUTTON
300
369
398
402
NIL
show-again
NIL
1
T
OBSERVER
T

@#$#@#$#@
WHAT IS IT?
-----------
This model demonstrates subtraction of numbers stored in two's complement format.


HOW IT WORKS
------------
The two binary numbers are padded to eight bits.  Next we take the two's complement of the number being subtracted, to get its negative.  Finally, we add the two numbers.
If the carry out of the last column is different from the carry into it, then overflow occurs (assuming the number of digits is fixed).


HOW TO USE IT
-------------
The setup button generates two random numbers stored in two's complement format.

The slow-motion slider is an easy way to adjust the speed of the display so you can watch the digits change as the red arrow passes.  Set it to zero if you want to just see the answer quickly.  0.5 is a good setting for the first few steps.

The step button does whatever step comes next, and then stops so you can take notes.

The go button finishes the entire problem, at a speed set by the slow-motion slider.

The show-again button starts the exact problem from the beginning.  You may then click either the step button or the go button to see the same demonstration.

The quiz button generates a random problem and then asks you to determine the answer.  Commas and spaces are ignored, so you may use them to prevent copy errors.  

THINGS TO NOTICE
----------------
When two numbers of the same sign are subtracted, it is impossible to get an overflow error.

If you add two numbers that have the same bit in the left-most column, and the result has a different bit in that column, there is always an overflow error.  This is a different way to detect overflow.

No borrows are needed, ever!


THINGS TO TRY
-------------
Set the slow-motion to about .50 seconds (or slower) and press the step button a few times.  Watch the demonstration of each step.

Do each step by hand, then press step to check your work.

Press setup until you see a problem that you think will cause an overflow error.  Press run to see if it does overflow.


EXTENDING THE MODEL
-------------------
Modify the model to show fixed point representation; that is, specify a given number of digits to the right of the decimal place.

Allow the user to input the two numbers to be subtracted.

Display the decimal equivalent of the two numbers and the difference.


NETLOGO FEATURES
----------------
"ask other-digit-here" is used by the arrow to process the digit it is passing over.

"count" is used to report the number of agents in the given agentset.

"word" is used to put two inputs together and make them a string.

RELATED MODELS
--------------
Binary Counter, Addition in Other Bases, Signed Integer Representation

CREDITS AND REFERENCES
----------------------
This model was written by Crystal Barchet and Teresa 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 Carrigan.
Contact Teresa Carrigan for appropriate licenses for redistribution 
for profit.

To refer to this model in academic publications, please use: 
Barchet, C. and Carrigan, T. (2004). Two's Complement Subtraction model. 
Blackburn College, Carlinville, IL.

In other publications, please use: 
Copyright 2004 by Crystal R. Barchet and Teresa Carrigan.  All rights reserved.  

FOR MORE INFORMATION 
-------------------- 
For more information about two's complement subtraction and overflow detection, see one of the following textbooks:
[1] Null, L. and Lobur, J. "Essentials of Computer Organization and Architecture", First Edition, Jones & Bartlett,  pages 48-49; 51-53; 58-59.
[2] Dale, N. and Lewis, J. "Computer Science Illuminated", Second Edition, Jones and Bartlett,  page 40.
@#$#@#$#@
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

bottom
false
0
Rectangle -7566196 true true 0 270 298 297

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

negative
false
0
Rectangle -7566196 true true 1 135 298 164

plus
false
0
Rectangle -7566196 true true 138 17 161 284
Rectangle -7566196 true true 14 135 283 163

thin-arrow
true
0
Polygon -7566196 true true 150 0 0 150 120 150 120 293 180 293 180 150 300 150

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