Clojure programming language The ancient Egyptians were perhaps the first people

Question

Clojure programming language

The ancient Egyptians were perhaps the first people on earth to come up with the idea of binary arithmetic when they developed their method of division. The Egyptian Division method is a tabular calculation that lends itself to a straightforward computer implementation. The table starts out with a 1 in column a, the divisor in column b and the dividend in column c. Columns a and b are successively doubled until the value in column b is greater than the value in column c. For example, to divide 1960 by 56, we generate the following table:

a b c

1 56 1960

2 112 1960

4 224 1960

8 448 1960

16 896 1960

32 1792 1960

64 3584 1960

At this point, we add a fourth column initialized to zero and apply the following algorithm. If the number in column b is less than or equal to that of column c, we add column a to column d and subtract column b from column c. Otherwise, we leave the values in c and d unchanged. In either case, we halve (integer division) the values in both columns a and b. We stop when column a becomes less than 1. At this point, the answer resides in column d.

a b c d

64 3584 1960 0

32 1792 1960 0

16 896 168 32

8 448 168 32

4 224 168 32

2 112 168 32

1 56 56 34

0 28 0 35

Define a function named egypt/ that takes two arguments, the divisor and the dividend and returns the quotient. Example call: (egypt/ 1960 56) Your method should implement an iterative process. You may use neither multiplication nor division in your solution. Hint: define two functions named double and halve which do their calculations using just addition and/or subtraction. The halve function must run in sub-linear time. Both double and halve should be visible, not nested.

Show Clojure code.

Explanation / Answer

#!/usr/bin/env python """ Egypt -- command line Egyptian fraction generator D. Eppstein, UC Irvine, 5 Mar 2004 """ from __future__ import division from optparse import OptionParser from random import randint import operator import sys import math # ====================================================================== # Basic utility subroutines # ====================================================================== def count(n = 0): """ Generate successive integers starting with n. Just like itertools.count except that n can be a long. """ while True: yield n n += 1 def intString(x): """ String for integer x, obeying options.factor. """ if x < 2 or not options.factor: return str(x) factorization = itemCounts(factors(x)).items() factorization.sort() out = [] for p,e in factorization: if e > 1: out.append("%d^%d" % (p,e)) else: out.append(str(p)) return ".".join(out) def unitFractionString(dd): """ Construct string for 1/dd. """ if dd == 1: return "1" else: return "1/" + intString(dd) def egyptianFractionString(xx): """ Construct string for Egyptian fraction formed by list of denominators in xx. """ return " + ".join(map(unitFractionString,xx)) # ====================================================================== # Backtracking search structure # ====================================================================== def ok(xx,dd): """ Test whether we can extend Egyptian fraction xx by appending dd. Checks for duplications and violations of constraints in command-line options. Returns True if dd can be appended, False otherwise. """ if dd < 1: return False if options.odd and dd % 2 == 0: return False if options.square and isqrt(dd)**2 != dd: return False if options.length and len(xx) >= options.length: return False if options.maxden and dd > options.maxden: return False if options.minden and dd >sys.stderr, "Trying", egyptianFractionString(xx), "+", intString(nn)+"/"+intString(dd) if options.length: if len(xx) + estimatedLength(nn,dd) > options.length: return noSolutions() if len(xx) + 2 == options.length and method == egypt_greedy: return egypt_reduce(xx,nn,dd) # speed up without changing solution set if len(xx) + 1 == options.length: if nn != 1 or not ok(xx,dd): return noSolutions() return singleSolution(xx+(dd,)) return method(xx,nn,dd) def mustBeEven(): """ Generate a warning message for methods unable to produce only odd numbers. """ if options.odd: print "Method is incompatible with odd restriction." sys.exit(0) def mustBeSmall(n): """ Generate a warning message for methods unable to handle large numbers. """ print "Unable to handle inputs >=",n,"with these settings." sys.exit(0) def estimatedLength(nn,dd): """ Generate a conservative underestimate of the number of terms needed in any Egyptian fraction expansion of nn/dd. The idea is to let 1/u be the nearest unit fraction greater than nn/dd, and generate a greedy expansion that reaches a number in the half-open interval [nn/dd,1/u). Note that the terms of this expansion depend only on u; the inputs nn and dd are used only to compute u and to terminate the expansion (when it sums to at least nn/dd). """ if nn

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.