Planet Scheme

June 23, 2017

Programming Praxis

Leading Digits Of Powers Of 2

John D. Cook, a programmer who writes about mathematics (he would probably describe himself as a mathematician who writes about programming) recently wrote about the distribution of the leading digits of the powers of 2, observing that they follow Benford’s Law, which we studied in a previous exercise.

Your task is to write a program that demonstrates that the distribution of the leading digits of the powers of 2 follows Benford’s Law. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at June 23, 2017 09:00 AM

June 20, 2017

Programming Praxis

Mangarevan Counting

Six hundred years ago, the people of the French Polynesian island of Mangareva developed a mixed-radix counting system that combined binary and decimal elements to count from 1 to 799. They had no zero. The digits 1 through 9 had their normal decimal value. Digits K, P, T and V had values 10, 20, 40 and 80, respectively, so they increased in a binary progression. A number N was represented as N = nV + T + P + K + m, where n and m were digits; note that T, P and K did not have modifiers. Thus, 73 is represented as TPK3, 219 is represented as 2VTK9, and 799 is represented as 9VTPK9 in Mangarevan. You might enjoy this article in Nature and this article in the Proceedings of the National Academy of Sciences. Arithmetic is interesting: 1VPK9 + 1 = 1VT, and 3VPK3 + 2VTK9 = 6VK2.

Your task is to write programs that translate to and from Mangarevan counting numbers. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at June 20, 2017 09:00 AM

June 16, 2017

Programming Praxis

A Scheme Idiom

While I was reading some Scheme code recently, I discovered a delightful little Scheme idiom that could simplify some coding tasks. It looks like this:

> (define (make-accum n)
    (case-lambda
      (() n)
      ((m) (set! n (+ n m)) n)))
> (define a (make-accum 20))
> a
#<procedure>
> (a)
20
> (a 10)
30
> (a)
30

Variable a is a accumulator; define it to set its initial value, fetch its current value by calling it as a function, and increment it by calling it with a value. This works because function make-accum returns a function, defined by case-lambda, with a semantics that varies based on its arity: with no arguments, the function returns the value stored in the closure, and with a single argument, it increments the value stored in the closure and returns the new value. The actual value is stored inside the function closure so it is only available through the defined interface, making it “safer” in some sense. And the concept works for other data types than accumulators, as the solution page will show.

Your task is to describe a useful idiom in your favorite programming language. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at June 16, 2017 02:00 PM

June 13, 2017

Programming Praxis

Climb To A Prime

The British mathematician John Horton Conway, famous for inventing the Game of Life cellular automaton, made this conjecture:

Select a number, then compute its prime factors, with multiplicity; for instance, 90 = 2 × 32 × 5. Then “bring down” the exponent and write the resulting digits, forming a new number; for instance, the exponent of 2 in the above factorization is brought down, forming the number 2325. Repeat the process with the new number, and again, and so on; for instance, starting from 90, the chain is 90, 2325, 35231, 72719, where the chain terminates. I conjecture that the process will eventually terminate with a prime number.

At his YouTube channel, Numberphile revealed that the conjecture is false. The number 13532385396179 = 13 × 532 × 3853 × 96179, so at each step it replaces itself, resulting in an infinite loop that will never reach a prime, thus disproving the conjecture. The discoverer of that number, James Davis, is entitled to a $1000 prize from Conway.

Your task is to write a program that calculates the climb to a prime for a given input number. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at June 13, 2017 02:00 PM

June 09, 2017

Programming Praxis

Generating Large Random Primes

We studied Pocklington’s Criterion, which lets us quickly find large random primes, in a previous exercise. That algorithm generates a certified prime — a number that is proven to be prime — rather than a probable prime according to some pseudoprimality test.

Even though it’s not hard to generate a certified large prime, most cryptographic applications accept probable primes, primarily because it is much faster to generate a probable prime than a certified prime. Wikipedia explains the algorithm:

For the large primes used in cryptography, it is usual to use a modified form of sieving: a randomly chosen range of odd numbers of the desired size is sieved against a number of relatively small primes (typically all primes less than 65,000). The remaining candidate primes are tested in random order with a standard probabilistic primality test such as the Baillie-PSW primality test or the Miller-Rabin primality test for probable primes.

Your task is to write a program that implements the Wikipedia algorithm for generating large random probable primes. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at June 09, 2017 02:00 PM

June 06, 2017

Programming Praxis

Matrix Rotation

We have a two-part exercise today, based on a Microsoft interview question.

First, write a program to rotate an m × n matrix 90° to the right, as shown below; your solution should touch each matrix element only once:

    a b c
    d e f                 m j g d a
A = g h i        rot(A) = n k h e b
    j k l                 o l i f c
    m n o

Second, write a program to rotate a square matrix with n rows and columns in-place. where the source and target matrices are the same matrix and there is no intermediate matrix (be sure your solution works for both even and odd n):

    a b c d e                 u p k f a
    f g h i j                 v q l g b
B = k l m n o        rot(B) = w r m h c
    p q r s t                 x s n i d
    u v w x y                 y t o j e

Your task is to write the two programs that rotate matrices. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at June 06, 2017 09:00 AM

June 02, 2017

Programming Praxis

Second Largest Item

Today’s exercise is only slightly tricky:

Write a program to find the second largest item in an array. Use the least possible number of comparisons.

Your task is to write a program to find the second largest item in an array using the least possible number of comparisons. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at June 02, 2017 09:00 AM

May 30, 2017

Programming Praxis

Sieving A Polynomial

I watch Stack Overflow and Reddit for questions about prime numbers. Most of the questions are basic, many are confused, a few are interesting, and some are just bizarre. A recent question falls in the latter category:

I need to make a list of the prime factors with multiplicity of all the numbers up to 300,001 that are equivalent to 1 modulo 4. My strategy is to make a list of the numbers 1 modulo 4, then calculate the factors of each. I don’t know how to calculate factors, but I know it’s complicated, so I figure somebody has already built a factoring program and put it on the web. Does anybody know a web API that I can call to determine the factors of a number?

For instance, if we limit the numbers to 50, the desired output is:

5	(5)
9	(3 3)
13	(13)
17	(17)
21	(3 7)
25	(5 5)
29	(29)
33	(3 11)
37	(37)
41	(41)
45	(3 3 5)
49	(7 7)

Calling a web API 75,000 times is a spectacularly wrong way to build the list, but I pointed the questioner to Wolfram|Alpha. Long-time readers of this blog know how to solve the problem directly, which we will do in today’s exercise.

Your task is to write a program to factor all the numbers up to 300,001 that are equivalent to 1 modulo 4. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at May 30, 2017 09:00 AM

May 26, 2017

Programming Praxis

Hill Cipher

The Hill Cipher was invented by Lester Hill in 1929. A block cipher based on modular matrix multiplication, it was rather advanced for its time. The diffusion inherent in the algorithm makes it difficult to break manually, though it is easy to work back to the key if you have some known plaintext.

The Hill Cipher uses arithmetic, so you will need to convert the alphabetic plaintext to numbers using a polybius square, a straddling checkboard, or the simple expedient of mapping A to 0, B to 1, and so on, until Z is 25, which we will adopt here. Our alphabet has 26 characters, which can be a problem since 26 = 2 × 13 is composite; the alphabet size becomes the modulus of the cipher system, and some keys won’t work, though it is easy to find keys that do. If you’re worried, add characters to the alphabet until it has a prime number of elements; for instance, you might choose a 29-character alphabet with the letters A to Z, a space character, a period, and a slash for a digit shift.

Let’s look at an example. We will send the message PROGRAMMINGPRAXIS with blocksize 3. The plaintext is padded with a Z, forming a 6 × 3 matrix:

    P R O   15 17 14
    G R A    6 17  0
P = M M I = 12 12  8
    N G P   13  6 15
    R A X   17  0 23
    I S Z    8 18 25

We must choose a key that is invertible; that is, a key that has an inverse (some textbooks call such keys non-singular). For a normal matrix to be invertible, the discriminant must be non-zero. Since we are using modular arithmetic instead of normal integer arithmetic, we have the additional requirement that the determinant and modulus must be coprime. If the first key you choose doesn’t work, try another. The key that we choose, and its mod 26 inverse, are:

    G Y B    6 24  1               8  5 10   I F K
K = N Q K = 13 16 10    inverse = 21  8 21 = V I V
    U R P   20 17 15              21 12  8   V M I

Encryption is performed by modular matrix multiplication, with C = P × K (mod 26):

    15 17 14              19 12  5   T M F
     6 17  0    6 24  1   23  0 23   X A U
C = 12 12  8 * 13 16 10 = 24 18 18 = Y S S
    13  6 15   20 17 15   14 13 12   O N M
    17  0 23              16 19 24   Q T Y
     8 18 25               2 21 17   C V R

So the ciphertext is TMFXAUYSSONMQTYCVR.

Decryption is also performed by modular matrix multiplication, with P = C × Kinv (mod 26):

    19 12  5              15 17 14   P R O
    23  0 23    8  5 10    6 17  0   G R A
P = 24 18 18 * 21  8 21 = 12 12  8 = M M I
    14 13 12   21 12  8   13  6 15   N G P
    16 19 24              17  0 23   R A X
     2 21 17               8 18 25   I S Z

Your task is to write a program that performs encryption and decryption using the Hill Cipher. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at May 26, 2017 09:00 AM

May 23, 2017

Programming Praxis

Matrix Determinant And Inverse

Today’s exercise is preliminary to the exercise we will have later this week. You are to write programs that calculate the determinant and inverse of a matrix. I won’t go into the math involved behind the matrix arithmetic, as there are many sources on the internet that know far more about the process than I. Google for “matrix determinant” or “matrix inverse”; I used YouTube for my instruction.

Your task is to write programs that calculate the determinant and inverse of a matrix. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at May 23, 2017 09:00 AM

May 22, 2017

GNU Guix

GNU Guix and GuixSD 0.13.0 released

We are pleased to announce the new release of GNU Guix and GuixSD, version 0.13.0!

The release comes with GuixSD USB installation images, a virtual machine image of GuixSD, and with tarballs to install the package manager on top of your GNU/Linux distro, either from source or from binaries.

It’s been 5 months since the previous release, during which 83 people contribute code and packages. The highlights include:

  • Guix now supports aarch64 (64-bit ARM processors). This release does not include a binary installation tarball though, and our build farm does not provide aarch64 substitutes yet. We are looking for aarch64 hardware to address this. Please get in touch with us if you can help!
  • Likewise, this release no longer includes a mips64el tarball, though Guix still supports that platform. We do not know whether we will continue to support mips64el in the long run; if you’d like to weigh in, please email us on guix-devel@gnu.org!
  • The GuixSD installation image now supports UEFI. GuixSD can also be installed on Btrfs now.
  • GuixSD has support to run system services (daemons) in isolated containers as a way to mitigate the harm that can be done by vulnerabilities in those daemons. See this article from April.
  • A new guix pack command to create standalone binary bundles is available. We presented it in March.
  • Guix now runs on the brand-new 2.2 series of GNU Guile. The transition led to hiccups that we have been addressing, in particular for users of guix pull. Among other things though, the noticeable performance improvement that comes for free is welcome!
  • guix publish, which is what we use to distribute binaries, has a new --cache operation mode that improves performance when distributing binaries to a large number of users, as is the case of our build farm.
  • Many reproducibility issues found in packages have been addressed—more on that in a future post.
  • 840 new packages, leading to a total of 5,400+, and many updates, including glibc 2.25, Linux-libre 4.11, and GCC 7.
  • New system services for Redis, Exim, Open vSwitch, and more. The interface of existing services, notably that of the NGINX service, has been greatly improved.
  • Many bug fixes!

See the release announcement for details.

About GNU Guix

GNU Guix is a transactional package manager for the GNU system. The Guix System Distribution or GuixSD is an advanced distribution of the GNU system that relies on GNU Guix and respects the user&aposs freedom.

In addition to standard package management features, Guix supports transactional upgrades and roll-backs, unprivileged package management, per-user profiles, and garbage collection. Guix uses low-level mechanisms from the Nix package manager, except that packages are defined as native Guile modules, using extensions to the Scheme language. GuixSD offers a declarative approach to operating system configuration management, and is highly customizable and hackable.

GuixSD can be used on an i686 or x86_64 machine. It is also possible to use Guix on top of an already installed GNU/Linux system, including on mips64el, armv7, and aarch64.

by Ludovic Courtès (guix-devel@gnu.org) at May 22, 2017 01:30 PM

May 19, 2017

Programming Praxis

Just Showing Off

As I have mentioned on several previous occasions, I frequently receive email from students asking for homework help, which I routinely ignore. Less frequently, I receive email from someone who tells me that Scheme is a horrible programming language, they don’t understand it, it is unreadable, there are too many parentheses, blah, blah, blah, and wouldn’t it be better if I wrote my blog in C#. (I don’t know what’s wrong with C# people, but I get more of them than any other language zealots.) Usually I ignore them, too, but the other day I engaged one of those correspondents who singled out macros as a particular wart on the face of Scheme. So I wrote to him and gave him this macro, which I used to calculate fibonacci numbers; the whole story is on the next page:

(define-syntax define-memoized
  (syntax-rules ()
    ((define-memoized (f arg ...) body ...)
      (define f
        (let ((cache (list)))
          (lambda (arg ...)
            (cond ((assoc `(,arg ...) cache) => cdr)
            (else (let ((val (begin body ...)))
                    (set! cache (cons (cons `(,arg ...) val) cache))
                    val)))))))))

When I showed him how to speed up the calculation of fibonacci numbers by memoizing sub-computations, he grudgingly agreed there might be something there, but it wouldn’t translate to C# (I didn’t disagree with that comment).

Your task is to write a program that shows off some special feature of your favorite programming language; tell the story how it makes your language better than any others, and give a real-life example. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at May 19, 2017 09:00 AM

May 16, 2017

Programming Praxis

License Plates

A license plate number has form ABC-123, three letters followed by three digits. You are to store the set of license plate numbers, assume you will have about a hundred thousand of them, and be able to answer queries like:

* Is license plate PLB-123 a member of the set?

* How many license plates begin with the letters PLB?

* What is the list of license plates that begin with the letters PLB?

Your task is to write programs to store and query a list of license plate numbers. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at May 16, 2017 09:00 AM

May 12, 2017

Programming Praxis

Division By Repeated Subtraction

I traded several emails this week with a programming student who was having trouble with this assignment:

Write a function that divides two numbers and returns their quotient. Use recursive subtraction to find the quotient.

The student went on to explain that he thought he needed to use a counter variable that he incremented each time the function recurred, but he didn’t know how to do that because the function could only take two arguments; it had to be of the form (define (divide a b) ...).

Your task is to write the function, and explain to the student how it works. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at May 12, 2017 09:00 AM

May 09, 2017

Programming Praxis

Distinct Characters

We’ve done similar exercises in the past:

Write a program to determine if all the characters in a string are distinct. For instance, the word “Programming” has two m and two g, so all the characters are not distinct, but the word “Praxis” has six distinct characters.

Your task is to write a program to determine if all the characters in a string are distinct; you should provide three solutions, one that takes time O(n²), one that takes time O(n log n), and one that takes time O(n). When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at May 09, 2017 09:00 AM