Planet Scheme

May 31, 2016

Programming Praxis

Learn A New Language

It’s fun to learn new programming languages. It’s also useful, even if you never use the new language, because it forces you to think differently about how you do things.

Your task is to write a familiar program in an unfamiliar language. When you are finished, you are welcome to read or run ([1], [2]) a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at May 31, 2016 12:00 PM

May 27, 2016

Programming Praxis

Pollard’s Rho Algorithm For Discrete Logarithms

We studied discrete logarithms in two previous exercises. Today we look at a third algorithm for computing discrete algorithms, invented by John Pollard in the mid 1970s. Our presentation follows that in the book Prime Numbers: A Computational Perspective by Richard Crandall and Carl Pomerance, which differs somewhat from other sources.

Our goal is to compute l (some browsers mess that up; it’s a lower-case ell, for “logarithm”) in the expression glt (mod p); here p is a prime greater than 3, g is an integer generator on the range 1 ≤ g < p, and t is an integer target on the range 1 ≤ g < p. Pollard takes a sequence of integer pairs (ai, bi) modulo (p − 1) and a sequence of integers xi modulo p such that xi = tai gbi (mod p), beginning with a0 = b0 = 0 and x0 = 1. Then the rule for deriving the terms of the various sequences is:

  • If 0 < xi < p/3, then ai+1 = (ai + 1) mod (p − 1), bi+1 = bi, and xi+1 = t xi (mod p).
  • If p/3 < xi < 2p/3, then ai+1 = 2 ai mod (p − 1), bi+1 = 2 bi mod (p − 1), and xi+1 = xi2 mod p.
  • If 2p/3 < xi < p, then ai+1 = ai, bi+1 = (bi + 1) mod (p − 1), and xi+1 = g xi mod p.

Splitting the computation into three pieces “randomizes” the calculation, since the interval in which xi is found has nothing to do with the logarithm. The sequences are computed until some xj = xk, at which point we have taj gbj = tak gbk. Then, if ajaj is coprime to p − 1, we compute the discrete logarithm l as (ajak) lbkbj (mod (p − 1)). However, if the greatest common divisor of ajaj with p − 1 is d > 1, then we compute (ajak) l0bkbj (mod (p − 1) / d), and l = l0 + m (p − 1) / d for some m = 0, 1, …, d − 1, which must all be checked until the discrete logarithm is found.

Thus, Pollard’s rho algorithm consists of iterating the sequences until a match is found, for which we use Floyd’s cycle-finding algorithm, just as in Pollard’s rho algorithm for factoring integers. Here are outlines of the two algorithms, shown side-by-side to highlight the similarities:

# find d such that d | n      # find l such that g**l = t (mod p)
function factor(n)            function dlog(g, t, p)
  func f(x) := (x*x+c) % n      func f(x,a,b) := ... as above ...
  t, h, d := 1, 1, 1            j := (1,0,0); k := f(1,0,0)
  while d == 1                  while j.x <> k.x
    t = f(t)                      j(x,a,b) := f(j.x, j.a, j.b)
    h = f(f(h))                   k(x,a,b) := f(f(k.x, k.a, k.b))
    d = gcd(t-h, n)             d := gcd(j.a-k.a, p-1)
  return d                      return l ... as above ...

Please pardon some abuse of notation; I hope the intent is clear. In the factoring algorithm, it is possible that d is the trivial factor n, in which case you must try again with a different constant in the f function; the logarithm function has no such possibility. Most of the time consumed in the computation is the modular multiplications in the calculations of the x sequence; the algorithm itself is O(sqrt p), the same as the baby-steps, giant-steps algorithm of a previous exercise, but the space requirement is only a small constant, rather than the O(sqrt p) space required of the previous algorithm. In practice, the random split is made into more than 3 pieces, which complicates the code but speeds the computation, as much as a 25% improvement on average.

Your task is to write a program that computes discrete logarithms using Pollard’s rho algorithm. 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 27, 2016 12:59 PM

May 24, 2016

Programming Praxis

Test Scores

The high school two blocks from me just had their annual picnic, my youngest daughter just graduated from college, and my primarily academic readership suddenly dropped in half (history suggest it will stay low until mid-August), so it seems to be the right season to have a simple data-processing task involving student test scores.

Given a list of student names and test scores, compute the average of the top five scores for each student. You may assume each student has as least five scores.

Your task is to compute student scores as described above. 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 24, 2016 09:00 AM

May 20, 2016

Programming Praxis

No Exercise Today

I’ve been busy at work and haven’t had time to prepare an exercise for today. I apologize.

Your task is to solve a previous exercise that you haven’t yet solved. Have fun!


by programmingpraxis at May 20, 2016 09:00 AM

May 17, 2016

Programming Praxis

Conditional Heap Insertion

This is an Amazon interview question:

Given a heap (priority queue), insert an element into the heap if the element is not already present in the heap. Your solution must work in O(n) time, where n is the number of items in the heap.

Your task is to write a program to insert an element into a heap if the element is not already present in the heap, in logarithmic time. 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 17, 2016 09:00 AM

May 13, 2016

Programming Praxis

Interleaved Increasing-Decreasing Sort

This must be somebody’s homework:

Given an array of integers, rearrange the elements of the array so that elements in even-indexed positions are in ascending order and elements in odd-indexed positions are in descending order. For instance, given the input 0123456789, the desired output is 0927456381, with the even-indexed positions in ascending order 02468 and the odd-indexed positions in descending order 97531.

Your task is to write a program that performs the indicated rearrangement of its input. 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 13, 2016 09:00 AM

May 12, 2016

Grant Rettke

If You Like LISP Then You’ll Love APL

Notes on Transcription of a talk given by Professor Perlis at the APL’78 Conference held at Foothill College, Los Altos, CA. on 1978-03-29 revealed these gems:

  • Contains all of the best attributes of written language
  • Contains all of the best attributes of LISP… just more so
  • Is a lyrical language

Notes follow…

Paragraphs starting at 1:

  • 1
    • Apostate: someone whose beliefs have changed and who no longer belongs to a religious or political group
    • “under the influence”
    • “Like all people who enter interesting things late in life, one tends to go over one’s head very quickly.”
  • 2
    • Row order: Bauer|Perlis|Dijkstra
  • 3
    • “My God, there must be something in this language (APL).”
    • APL takes on the properties of the viewer
  • 4
    • “What attracted me, then, to APL was a feeling that perhaps through APL one might begin to acquire some of the dimensions in programming that we revere in natural language — some of the pleasures of composition; of saying things elegantly; of being brief, poetic, artistic, that makes our natural languages so precious to us. That aspect of programming was one that I’ve long been interested in but have never found any level for coming close to in my experience with (other) languages”
      • WOW
    • “It was clear in those languages that programming was really an exercise in plumbing. One was building an intricate object, and the main problem was just to keep your head above water. But, so difficult is it to keep your head above water with those languages”
  • 5
    • It’s unnecessary that APL ever run on a computer: 1963
      • Notation for expressing algorithmic concepts
    • Happy accident: System 360 and Iverson not at Harvard
  • 6
    • His interests don’t like up with the majority
    • APL is approaching a kind of completeness
    • Every user approaches APL differently
    • People don’t mind using a language if they get things done and feel kind of good doing it; no matter how bad the language it
    • FORTRAN will pay bills for a long time; don’t throw APL (aka have a bowel movement) in people’s Wheaties
    • About every language ever

      And it certainly shouldn’t be a goal of people who use APL to stand forth and
      say, “Why do you jackasses use these inferior linguistic vehicles when we have
      something here that’s so precious, so elegant, which gives me so much
      pleasure? How can you be so blind and so foolish?” That debate you’ll never
      win, and I don’t think you ought to try.
      
  • 7
    • Adding new language features tends to add new problems
  • 8
    • WOW follows

      What many of us forget — and we should never forget, of course — is that
      programming step-by-step must someday, though we don’t know how, reach the
      point where it is universally capable of expressing our thoughts, at least
      insofar as they involve giving prescriptions on how to do things. Programming
      is thinking — not all thinking yet, and maybe never all thinking — but insofar
      as when we sit down at the computer we are faced with so many attractive
      possibilities which never occurred to us until we programmed, insofar as that
      happens, we are going to be dissatisfied with the programming languages we
      have. And that includes every language that’s ever been created and those yet
      to come — and there will be others yet to come.
      
  • 9
    • The idea that one language is perfect for teaching is false
    • The invention of constructions is “learning to program”
    • We curse those inventions, but that which we must invent will never be there, so it must be invented
      • Reminiscent of LISP
    • We invent (construct) more and more, killing elegance
  • 10
    • …the quest for the perfect”
      • Makes me think of LISP
    • Every language is the language of tomorrow
    • APL has something extra though
  • 11
    • “LISP has a very precious character, if indeed there are some people who can express programming ideas to other people in the language in which they program.”
      • WOW
    • APL has this property to a far greater degree
    • WOW follows

      I can’t do that with ALGOL; never have I been able to do it with ALGOL.
      Whenever I’ve programmed in ALGOL and I’ve wished to make some statements
      about the program I was writing, I was forced to go outside the language and
      use English, or mathematics, or some block diagrams or what-not. In APL, I
      find that to a far greater degree than any other language that I’ve used, I
      can make statements about the programs that I’m writing, in APL — actually not
      exactly APL, but APL with some nice little extensions that I dream up at the
      moment but would never think of implementing. But by and large, I find that
      the language allows me to express myself, in the language, about the things
      I’m dealing with. I find that a very precious property of a programming
      language.
      
  • 12
    • APL is lyrical
    • Programming APL is fun, charming, and pleasant
      • Perl?
    • Only one way to do things make programming dull
      • Perlis, certainly LISPism
  • 13
    • “God made us all different.”
    • You can say things different ways using language
    • Makes reading fun
    • … it’s a pleasure to read (something) when it’s written by someone who has that talent”
    • “If Shakespeare were alive today, he’d be a programmer, and he’d be writing one-liners in APL.”
      • WOW
  • 14
    • 1 problem, 50 people, 40 different solutions
    • Lets people think originally and possibly poorly
    • Gives APL a literary quality
    • Efficiency is important, so are infinite other criteria
  • 15
    • Elegant and clever are praiseworthy
    • “My God, that’s wonderful! That’s a mechanism!”
  • 16
    • “APL Pornography” “thrives not because we’re evil, but because we’re human”
    • ONE liners are the first step in learning APL
      • Never use control structures when you are first learning
  • 17
    • Eventually everything “just fits”
  • 18
    • Avoid the “the dumbbell model of a language” utilization
      • High at both ends
      • Barely used in the middle
  • 19
    • APL is not perfect, no language is
    • “the commerce of programs” will not elevate APL to the next level
  • 20
    • NA
  • 21
    • Fortran was built for the hardware
    • APL wasn’t built to fit computers
      • A stream processing language, parallel?
  • 22
    • Thoughts about how to realize the stream model
  • 23
    • “we’ve got to get BASIC out of the public school system. BASIC is really harmful for young people. It’s all right for old-timers.”
    • “once you’ve learned APL, you know BASIC, you know FORTRAN, you know ALGOL, indeed, I think you know all programming languages. You don’t know how you know them, but you know them.”
  • 24
    • “arrays, by-and-large, are used by you as control carriers through which you blast sequences of operations. And the use of rank is merely a convenient method of carrying small arrays on the backs of larger arrays. ”
  • 25
    • NA
  • 26
    • “Hardware drives our field”
    • “APL is just the ideal language, or closer than any other language, for using that real estate”

by Grant at May 12, 2016 11:12 PM

May 10, 2016

Programming Praxis

Concatenate N N Times

A number like 7777777 consists of the number 7 concatenated to itself 7 times. A number like 121212121212121212121212 consists of the number 12 concatenated to itself 12 times.

Your task is to write a program that calculates the number that is concatenated to itself the number of times as the number is (that’s hard to say). 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 10, 2016 09:00 AM

May 06, 2016

Programming Praxis

Baby Steps, Giant Steps

In a previous exercise we discussed the discrete logarithm problem, which is to compute the exponent y in the expression xyn (mod m), given x, n, and m; the modulus m is usually taken as prime. Today we look at an algorithm, known as baby steps, giant steps, that was developed by Daniel Shanks in 1971:

1. Compute limits:

b = ⌈ √m

h = (x−1)b

2. Construct lists:

A = { xi : i = 0, 1, …, b − 1 } // giant steps

B = { n hj : j = 0, 1, …, b − 1 } // baby steps

3. Sort and find intersection:

Sort the lists A and B

Find an intersection, say xi = n hj

Return y = i + j b

Since m is prime, there must be some y ∈ [0, m) for which xyn (mod m). Write y = i + j b, where b = ⌈ √m ⌉. Since y must exist, so too i (which counts the giant steps) and j (which counts the baby steps) must exist, and there must be an intersection between the baby steps and the giant steps.

Time complexity is obviously O(sqrt m), which beats the O(m) time complexity of the brute-force algorithm of the previous exercise. There are better algorithms for computing discrete logarithms, which we will study in future exercises.

Your task is to write a program that calculates discrete logarithms using the baby steps, giant steps algorithm. 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 06, 2016 09:00 AM

May 03, 2016

Programming Praxis

Discrete Logarithms

The discrete logarithm problem is to compute the exponent y in the expression xyn (mod m), given x, n, and m; x and m must be relatively prime, which is usually enforced by taking the modulus m as prime. For instance, in the expression 3y ≡ 13 (mod 17), the discrete logarithm y = 4, since 34 ≡ 13 (mod 17). The discrete logarithm problem is of fundamental importance in some branches of cryptography, and bears many similarities to factoring integers. Although we have states the discrete logarithm problem using integers, in many cases some other group is used, for instance calculating discrete logarithms on an elliptic curve.

The simplest algorithm for finding the discrete logarithm is simply to try each y from 0 to m; if m is prime, one of the y is certain to work. Unfortunately, this algorithm is very slow, taking time O(m). We’ll see better algorithms in future exercises; our purpose today is to introduce the concept of the discrete logarithm, and to provide a known good algorithm as a base for testing future algorithms.

Your task is to write a program that computes discrete logarithms by trying each possible value in succession until the answer is found. 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 03, 2016 09:00 AM

May 01, 2016

Grant Rettke

Chez Scheme Now Open Source

The other night I was daydreaming about buying a Chez Scheme license so I checked up on their license costs.

They are now Apache Licensed OSS.

Funny timing as they opened up only days prior.

The issue board is already active.

#chez on Freenode is blessed though the channel doesn’t seem to be up yet.

This is all delightful.

by Grant at May 01, 2016 03:13 PM

April 29, 2016

Programming Praxis

Binary Search

I goofed.

While writing a program (it may appear in a future exercise) I needed to search a sorted array for a target value. I should have copied an existing binary search, but instead I wrote my own, since I’m a good programmer and can certainly write a simple function like that. You won’t have any trouble guessing what happened next.

Your task is to write a binary search function; do it yourself, without looking at any library implementations or searching the internet. You might also want to write a test script to give you confidence in your function. 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 April 29, 2016 09:00 AM

April 28, 2016

The Racket Blog

Racket v6.5

Racket version 6.5 is now available from http://racket-lang.org/
  • Typed Racket and the racket/contract library generate code with lower overhead, speeding up typed/untyped interaction in a number of gradual typing programs we studied.
  • Macros written using syntax-parse automatically emit more accurate error messages.
  • The contract profiler captures costs from more contract combinators, including all those in the main distribution.
  • Hash table and set iteration, via both existing and new non-generic sequences, is more performant, up to twice as fast on microbenchmarks.
  • The Racket optimizer detects many more optimization opportunities, including when variables always hold numbers.
  • The db library supports single-result CALL statements in MySQL.
  • The net/dns library supports SRV records.
  • The racket/unix-socket library supports listen and accept operations.

The following people contributed to this release:
Adrien Tateno, Alex Knauth, Alexander Shopov, Alexis King, Andrew Kent, Asumu Takikawa, Ben Greenman, Chen Xiao, Chris Jester-Young, Daniel Feltey, Eric Dobson, Georges Dupéron, Gustavo Massaccesi, Ian Harris, Jay McCarthy, Jens Axel Søgaard, John Clements, Leandro Facchinetti, Lehi Toskin, Leif Andersen, Łukasz Dąbek, Marc Kaufmann, Matthew Flatt, Matthias Felleisen, Michael McConville, Mike Sperber, Paul Stansifer, Philippe Meunier, Robby Findler, Rodrigo Setti, Ryan Culpepper, Sam Caldwell, Sam Tobin-Hochstadt, Sorawee Porncharoenwase, Spencer Florence, Stephen Chang, Tony Garnock-Jones, Vincent St-Amour, WarGrey Gyoudmon Ju, and William J. Bowman.

Feedback Welcome

by Ryan Culpepper (noreply@blogger.com) at April 28, 2016 07:55 PM

April 26, 2016

Programming Praxis

An Integer Formula For Fibonacci Numbers

Today’s exercise isn’t really an exercise but an astonishing integer formula for computing the nth Fibonacci number; here it is in Python:

def fib(n):
    return (4 << n*(3+n)) // ((4 << 2*n) − (2 << n) − 1) & ((2 << n) − 1)

You can see an explanation here and discussion here.

Your task is to translate the program to your favorite 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 April 26, 2016 09:00 AM

April 24, 2016

GNU Guix

GNU Guix welcomes four students for GSoC

We are glad to announce that four students will join GNU Guix for the 2016 Google Summer of Code (GSoC):

All four projects sound exciting to us and we are happy to see progress on these fronts. Happy hacking!

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's 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 and armv7.

by Ludovic Courtès at April 24, 2016 07:45 PM