Re: [racket-users] Long division algorithm in HtDP way

[Matthias Felleisen]

I couldn’t help myself. So here is 90% of what John proposed in HtDP’s ISL+ 
language. Exercise for the reader: fix the failing tests. 


#lang htdp/isl+

;; long division

;; Trace = [cons N [cons N [Listof [List N N]]]

;; N N -> Trace 
;; compute the trace for the division of x and y 

;; example, worked 
;; 5432 : 12 = 452
;;-48
;;--
;;  63
;; -60
;;  --
;;   32
;;  -24
;;   --
;;8
;;=

(check-expect (long 5432 12) (list 452 8 (list 54 48) (list 32 24)))
(define (long x y)
  (local ((define x-as-digits (number->digits x))
  (define result  (long-helper (list (first x-as-digits)) (rest 
x-as-digits) y))
  (define quotient(digits->number (first result
(list quotient (second result


;; [Listof Digit] [Listof Digit] N -> Trace 
;; compute the trace of a long division of (digits->number (append fst-digits 
rest-digits)) by y
(check-expect (long-helper '(5) '(4 3 2) 12) (list 452 8 (list 54 48) (list 32 
24)))
(define (long-helper fst-digits rest-digits y)
  (local ((define fst-number (digits->number fst-digits)))
(cond
[(< fst-number y)
 (if (empty? rest-digits)
 (list '() fst-number)
 (long-helper (snoc fst-digits (first rest-digits)) (rest rest-digits) 
y))]
[(= fst-number y) (list (list 1) 0)]
[else (local ((define next-digit (subtract-often-enough fst-number y))
  (define remainder  (- fst-number (* next-digit y)))
  (define result (long-helper (list remainder) rest-digits 
y))
  (define quotient   (first result))
  (define remainder2 (second result)))
(list (cons next-digit quotient) remainder2))])))

;; N N -> [List N N]
;; subtract y from x until x < y
(check-expect (subtract-often-enough 54 12) 4)
(define (subtract-often-enough x y)
  (cond
[(< x y) 0]
[else (+ (subtract-often-enough (- x y) y) 1)]))

;; [Listof X] X -> [Listof X]
;; add x to end of l
(check-expect (snoc '() 1) '(1))
(check-expect (snoc '(1) 2) '(1 2))
(define (snoc l x)
  (append l (list x)))

;; [listof Digit] -> N
;; render the given sequence of digits as a number
(check-expect (digits->number '(1 2 3)) 123)
(define (digits->number digits)
  (string->number (implode (map number->string digits

;; N -> [Listof Digit]
;; split number into sequence of digits
(check-expect (number->digits 123) '(1 2 3))
(define (number->digits x)
  (map string->number (explode (number->string x

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] Long division algorithm in HtDP way

[Matthias Felleisen]

Let me support John’s email with a hint: 

#lang htdp/isl+

;; long division

;; Number Number -> (cons Number (cons Number [Listof Number]))
;; compute the list of steps needed to divide x by y

;; work thru an example
;; given  5432, 12
;; wanted [list 452 8) ... optional: (list 54 48) (list 63 60) (list 32 24)]
;; because 
;; (quotient 5432 12) = 12
;; (remainder 5432 12) = 8
;; IGNORE the trace part 

(define (long x y)
  (cond
[(< x y) (list 0 x)]
[(= y x) (list 1 0)]
[else (local ((define r (long (- x y) y))
  (define quotient  (first r))
  (define remainder (second r)))
(list (+ quotient 1) remainder))]))

(long 5432 12)




> On Sep 7, 2017, at 2:09 PM, 'John Clements' via Racket Users 
>  wrote:
> 
> 
>> On Sep 7, 2017, at 9:28 AM, jaroslaw.mo...@gmail.com wrote:
>> 
>> 
>> Dear Racketeers!
>> 
>> I would like to write the function divide in racket, for performing the long 
>> division, which would print the whole computational process, as the 
>> elementary school pupils do. For example, the call (divide 5432, 12) should 
>> print this:
>> 
>> 5432 : 12 = 452
>> -48
>> --
>> 63
>> -60
>> --
>>  32
>> -24
>>  --
>>   8
>>   =
> 
> Sounds like fun! 
> 
> If I were you, I would separate this into two problems.
> 
> 1) given the divisor and the divisee, produce a “trace” of the division.
> 2) given a “trace”, produce a (single multi-line) string representing it.
> 
> Most of the thinking will be in developing the data definition for the 
> “trace. ” Once this is done, the rest should be pretty straightforward.
> 
> John Clements
> 
> -- 
> You received this message because you are subscribed to the Google Groups 
> "Racket Users" group.
> To unsubscribe from this group and stop receiving emails from it, send an 
> email to racket-users+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.