#lang racket

;; we are told to assume these are already defined.
(define (double x)
  (+ x x))
(define (halve x)
  (/ x 2))

;; multiplication. defined in terms of addition, double and halve.
;; logarithmic time, constant space.
(define (mult x y)
  (define (recc x y a)
    (cond
      ((= y 0) a)
      ((even? y) (recc (double x) (halve y) a))
      (else (recc x (- y 1) (+ a x)))))
  (recc x y 0))