The Lumber Room

"Consign them to dust and damp by way of preserving them"

Printing floating-point numbers

Everyone knows that floating-point numbers, being discrete, cannot possibly exactly represent every real number. In particular, the usual binary (IEEE 754) floating point numbers cannot even exactly store all numbers exactly representable in decimal (e.g. 0.3 or 0.1, which are not dyadic rationals).

Just because the number stored internally is not 0.1 but the closest approximation to it (say as 0.100000001490116119384765625) doesn’t mean it should be printed as such, when “0.1” means exactly the same number.

This is a solved problem since 1990.

TODO: Write rest of this post.

Bryan O’Sullivan (of Real World Haskell fame):

Steel & White paper How to Print Floating-Point Numbers Accurately: https://lists.nongnu.org/archive/html/gcl-devel/2012-10/pdfkieTlklRzN.pdf

Their retrospective: http://grouper.ieee.org/groups/754/email/pdfq3pavhBfih.pdf

Burger & Dybvig:
http://www.cs.indiana.edu/~dyb/pubs/FP-Printing-PLDI96.pdf

Russ Cox: http://research.swtch.com/ftoa

Written by S

Wed, 2015-04-01 at 16:50:47

Posted in Uncategorized

Kalidasa’s Deepashikha

(Another example of good vs bad translations from Sanskrit. Previously see here and here.)

One of Kālidāsa’s famous similes is in the following verse from the Raghuvaṃśa, in the context of describing the svayaṃvara of Indumatī. The various hopeful suitors of the princess, all kings from different regions, are lined up as she passes them one by one, her friend doing the introductions.

संचारिणी दीपशिखेव रात्रौ
यम् यम् व्यतीयाय पतिंवरा सा ।
नरेन्द्रमार्गाट्ट इव प्रपेदे
विवर्णभावम् स स भूमिपालः ॥ ६-६७


saṁcāriṇī dīpa-śikheva rātrau
yam yam vyatīyāya patiṁvarā sā |
narendra-mārga-aṭṭa iva prapede
vivarṇa-bhāvam sa sa bhūmipālaḥ || 6-67

Only today did I discover a decent translation into English. It’s by John Brough (1975/6):

As if a walking lamp-flame in the night
On the king’s highway, flanked with houses tall,
She moved, and lit each prince with hopeful light,
And, passing on, let each to darkness fall.

Every other translation I have seen really falls short. Witness the misunderstandings, and the killing of all feeling.

Here is Ryder (1904), who is usually good:

And every prince rejected while she sought
A husband, darkly frowned, as turrets, bright
One moment with the flame from torches caught,
Frown gloomily again and sink in night.

The idea is there, but requires too much effort to understand.

This is P. de Lacy Johnstone (1902):

Now as the Maid went by, each suitor-King,
Lit for a moment by her dazzling eyes,
Like wayside tower by passing lamp, sank back
In deepest gloom. …

Every king, whom Indumati passed by while choosing her husband, assumed a pale look as the houses on a high way are covered with darkness in the absence of lamps.

Whatsoever king the maiden intent on choosing her husband passed by, like the flame of a moving lamp at night, that same king turned pale, just as a mansion situate on the highway, is shrouded in darkness when left behind (by a moving light).

Desiraju Hanumanta Rao

67. pati.m varA sA= husband, selector, she – she who has come to select her husband, indumati; rAtrau sa.mcAriNI dIpa shikha iva= in night, moving, lamp’s, [glittering] flame, as with; ya.m ya.m= whom, whom; [bhUmi pAlam= king, whomever]; vyatIyAya= passed by; saH saH bhUmipAlaH= he, he, king – such and such a king; narendra mArga= on king’s, way; aTTa= a turret, or a balustrade; iva= like; vi+varNa bhAva.m= without, colour, aspect – they bore a colourless aspect; prapede= [that king] obtained – that king became colourless, he drew blank.
Princess indumati who came to choose her husband then moved like the glittering flame of a lamp on a king’s way, and whichever prince she left behind was suffused with pallor just like a turret or balustrade on the king’s way will be shrouded in darkness and becomes dim when left behind by the moving light on the king’s way. [6-67]

And this is representative of the average quality of Sanskrit-to-English translations, and how much beauty is lost.

Written by S

Mon, 2015-02-09 at 20:04:42

Posted in sanskrit

Tagged with

Some playing with Python

A long time ago, Diophantus (sort of) discussed integer solutions to the equation

$\displaystyle x^2 + y^2 = z^2$

(solutions to this equation are called Pythagorean triples).

Centuries later, in 1637, Fermat made a conjecture (now called Fermat’s Last Theorem, not because he uttered it in his dying breath, but because it was the last one to be proved — in ~1995) that

$\displaystyle x^n + y^n = z^n$

has no positive integer solutions for $n \ge 3$. In other words, his conjecture was that none of the following equations has a solution:

$\displaystyle x^3 + y^3 = z^3$

$\displaystyle x^4 + y^4 = z^4$

$\displaystyle x^5 + y^5 = z^5$

$\displaystyle x^6 + y^6 = z^6$

… and so on. An nth power cannot be partitioned into two nth powers.

About a century later, Euler proved the $n = 3$ case of Fermat’s conjecture, but generalized it in a different direction: he conjectured in 1769 that an nth power cannot be partitioned into fewer than n nth powers, namely

$\displaystyle z^n = \sum_{i = 1}^k x_i^n$

has no solutions with $k < n$. So his conjecture was that (among others) none of the following equations has a solution:

$\displaystyle z^3 = a^3 + b^3$

$\displaystyle z^4 = a^4 + b^4 + c^4$

$\displaystyle z^5 = a^5 + b^5 + c^5 + d^5$

$\displaystyle z^6 = a^6 + b^6 + c^6 + d^6 + e^6$

… and so on.

This conjecture stood for about two centuries, until abruptly it was found to be false, by Lander and Parkin who in 1966 simply did a direct search on the fastest (super)computer at the time, and found this counterexample:

$\displaystyle 27^5 + 84^5 + 110^5 + 133^5 = 144^5$

(It is still one of only three examples known, according to Wikipedia.)

Now, how might you find this solution on a computer today?

In his wonderful (as always) post at bit-player, Brian Hayes showed the following code:

import itertools as it

def four_fifths(n):
'''Return smallest positive integers ((a,b,c,d),e) such that
a^5 + b^5 + c^5 + d^5 = e^5; if no such tuple exists
with e < n, return the string 'Failed'.'''
fifths = [x**5 for x in range(n)]
combos = it.combinations_with_replacement(range(1,n), 4)
while True:
try:
cc = combos.next()
cc_sum = sum([fifths[i] for i in cc])
if cc_sum in fifths:
return(cc, fifths.index(cc_sum))
except StopIteration:
return('Failed')


to which, if you add (say) print four_fifths(150) and run it, it returns the correct answer fairly quickly: in about 47 seconds on my laptop.

The if cc_sum in fifths: line inside the loop is an $O(n)$ cost each time it’s run, so with a simple improvement to the code (using a set instead) and rewriting it a bit, we can write the following full program:

import itertools

def find_counterexample(n):
fifth_powers = [x**5 for x in range(n)]
fifth_powers_set = set(fifth_powers)
for xs in itertools.combinations_with_replacement(range(1, n), 4):
xs_sum = sum([fifth_powers[i] for i in xs])
if xs_sum in fifth_powers_set:
return (xs, fifth_powers.index(xs_sum))
return 'Failed'

print find_counterexample(150)


which finishes in about 8.5 seconds.

Great!

But there’s something unsatisfying about this solution, which is that it assumes there’s a solution with all four numbers on the LHS less than 150. After all, changing the function invocation to find_counterexample(145) makes it run a second faster even, but how could we know to do without already knowing the solution? Besides, we don’t have a fixed 8- or 10-second budget; what we’d really like is a program that keeps searching till it finds a solution or we abort it (or it runs out of memory or something), with no other fixed termination condition.

The above program used the given “n” as an upper bound to generate the combinations of 4 numbers; is there a way to generate all combinations when we don’t know an upper bound on them?

Yes! One of the things I learned from Knuth volume 4 is that if you simply write down each combination in descending order and order them lexicographically, the combinations you get for each upper bound are a prefix of the list of the next bigger one, i.e., for any upper bound, all the combinations form a prefix of the same infinite list, which starts as follows (line breaks for clarity):

1111,
2111, 2211, 2221, 2222,
3111, 3211, 3221, 3222, 3311, 3321, 3322, 3331, 3332, 3333,
4111, ...
... 9541, 9542, 9543, 9544, 9551, ... 9555, 9611, ...


There doesn’t seem to be a library function in Python to generate these though, so we can write our own. If we stare at the above list, we can figure out how to generate the next combination from a given one:

1. Walk backwards from the end, till you reach the beginning or find an element that’s less than the previous one.
2. Increase that element, set all the following elements to 1s, and continue.

We could write, say, the following code for it:

def all_combinations(r):
xs = [1] * r
while True:
yield xs
for i in range(r - 1, 0, -1):
if xs[i] < xs[i - 1]:
break
else:
i = 0
xs[i] += 1
xs[i + 1:] = [1] * (r - i - 1)


(The else block on a for loop is an interesting Python feature: it is executed if the loop wasn’t terminated with break.) We could even hard-code the r=4 case, as we’ll see later below.

For testing whether a given number is a fifth power, we can no longer simply lookup in a fixed precomputed set. We can do a binary search instead:

def is_fifth_power(n):
assert n > 0
lo = 0
hi = n
# Invariant: lo^5 < n <= hi^5
while hi - lo > 1:
mid = lo + (hi - lo) / 2
if mid ** 5 < n:
lo = mid
else:
hi = mid
return hi ** 5 == n


but it turns out that this is slower than one based on looking up in a growing set (as below).

Putting everything together, we can write the following (very C-like) code:

largest_known_fifth_power = (0, 0)
known_fifth_powers = set()
def is_fifth_power(n):
global largest_known_fifth_power
while n > largest_known_fifth_power[0]:
m = largest_known_fifth_power[1] + 1
m5 = m ** 5
largest_known_fifth_power = (m5, m)
return n in known_fifth_powers

def fournums_with_replacement():
(x0, x1, x2, x3) = (1, 1, 1, 1)
while True:
yield (x0, x1, x2, x3)
if x3 < x2:
x3 += 1
continue
x3 = 1
if x2 < x1:
x2 += 1
continue
x2 = 1
if x1 < x0:
x1 += 1
continue
x1 = 1
x0 += 1
continue

if __name__ == '__main__':
tried = 0
for get in fournums_with_replacement():
tried += 1
if (tried % 1000000 == 0):
print tried, 'Trying:', get
rhs = get[0]**5 + get[1]**5 + get[2]**5 + get[3]**5
if is_fifth_power(rhs):
print 'Found:', get, rhs
break


which is both longer and slower (takes about 20 seconds) than the original program, but at least we have the satisfaction that it doesn’t depend on any externally known upper bound.

I originally started writing this post because I wanted to describe some experiments I did with profiling, but it’s late and I’m sleepy so I’ll just mention it.

python -m cProfile euler_conjecture.py


will print relevant output in the terminal:

         26916504 function calls in 26.991 seconds

Ordered by: standard name

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
1   18.555   18.555   26.991   26.991 euler_conjecture.py:1()
13458164    4.145    0.000    4.145    0.000 euler_conjecture.py:12(fournums_with_replacement)
13458163    4.292    0.000    4.292    0.000 euler_conjecture.py:3(is_fifth_power)
175    0.000    0.000    0.000    0.000 {method 'add' of 'set' objects}
1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}


Another way to view the same thing is to write the profile output to a file and read it with cprofilev:

python -m cProfile -o euler_profile.out euler_conjecture.py
cprofilev euler_profile.out


and visit http://localhost:4000 to view it.

Of course, simply translating this code to C++ makes it run much faster:

#include <array>
#include <iostream>
#include <map>
#include <utility>

typedef long long Int;
constexpr Int fifth_power(Int x) { return x * x * x * x * x; }

std::map<Int, int> known_fifth_powers = {{0, 0}};
bool is_fifth_power(Int n) {
while (n > known_fifth_powers.rbegin()->first) {
int m = known_fifth_powers.rbegin()->second  + 1;
known_fifth_powers[fifth_power(m)] = m;
}
return known_fifth_powers.count(n);
}

std::array<Int, 4> four_nums() {
static std::array<Int, 4> x = {1, 1, 1, 0};
int i = 3;
while (i > 0 && x[i] == x[i - 1]) --i;
x[i] += 1;
while (++i < 4) x[i] = 1;
return x;
}

std::ostream& operator<<(std::ostream& os, std::array<Int, 4> x) {
os << "(" << x[0] << ", " << x[1] << ", " << x[2] << ", " << x[3] << ")";
return os;
}

int main() {
while (true) {
std::array<Int, 4> get = four_nums();
Int rhs = fifth_power(get[0]) + fifth_power(get[1]) + fifth_power(get[2]) + fifth_power(get[3]);
if (is_fifth_power(rhs)) {
std::cout << "Found: " << get << " " << known_fifth_powers[rhs] << std::endl;
break;
}
}
}


and


clang++ -std=c++11 euler_conjecture.cc && time ./a.out


runs in 2.43s, or 0.36s if compiled with -O2.

But I don’t have a satisfactory answer to how to make our Python program which takes 20 seconds as fast as the 8.5-second known-upper-bound version.

Edit [2015-05-08]: I wrote some benchmarking code to compare all the different “combination” functions.

import itertools

# Copied from the Python documentation
def itertools_equivalent(iterable, r):
pool = tuple(iterable)
n = len(pool)
if not n and r:
return
indices = [0] * r
yield tuple(pool[i] for i in indices)
while True:
for i in reversed(range(r)):
if indices[i] != n - 1:
break
else:
return
indices[i:] = [indices[i] + 1] * (r - i)
yield tuple(pool[i] for i in indices)

# Above function, specialized to first argument being range(1, n)
def itertools_equivalent_specialized(n, r):
indices = [1] * r
yield indices
while True:
for i in reversed(range(r)):
if indices[i] != n - 1:
break
else:
return
indices[i:] = [indices[i] + 1] * (r - i)
yield indices

# Function to generate all combinations of 4 elements
def all_combinations_pythonic(r):
xs = [1] * r
while True:
yield xs
for i in range(r - 1, 0, -1):
if xs[i] < xs[i - 1]:
break
else:
i = 0
xs[i] += 1
xs[i + 1:] = [1] * (r - i - 1)

# Above function, written in a more explicit C-like way
def all_combinations_clike(r):
xs = [1] * r
while True:
yield xs
i = r - 1
while i > 0 and xs[i] == xs[i - 1]:
i -= 1
xs[i] += 1
while i < r - 1:
i += 1
xs[i] = 1

# Above two functions, specialized to r = 4, using tuple over list.
def fournums():
(x0, x1, x2, x3) = (1, 1, 1, 1)
while True:
yield (x0, x1, x2, x3)
if x3 < x2:
x3 += 1
continue
x3 = 1
if x2 < x1:
x2 += 1
continue
x2 = 1
if x1 < x0:
x1 += 1
continue
x1 = 1
x0 += 1
continue

# Benchmarks for all functions defined above (and the library function)
def benchmark_itertools(n):
for xs in itertools.combinations_with_replacement(range(1, n), 4):
if xs[0] >= n:
break
def benchmark_itertools_try(n):
combinations = itertools.combinations_with_replacement(range(1, n), 4)
while True:
try:
xs = combinations.next()
if xs[0] >= n:
break
except StopIteration:
return
def benchmark_itertools_equivalent(n):
for xs in itertools_equivalent(range(1, n), 4):
if xs[0] >= n:
break
def benchmark_itertools_equivalent_specialized(n):
for xs in itertools_equivalent_specialized(n, 4):
if xs[0] >= n:
break
def benchmark_all_combinations_pythonic(n):
for xs in all_combinations_pythonic(4):
if xs[0] >= n:
break
def benchmark_all_combinations_clike(n):
for xs in all_combinations_clike(4):
if xs[0] >= n:
break
def benchmark_fournums(n):
for xs in fournums():
if xs[0] >= n:
break

if __name__ == '__main__':
benchmark_itertools(150)
benchmark_itertools_try(150)
benchmark_itertools_equivalent(150)
benchmark_itertools_equivalent_specialized(150)
benchmark_all_combinations_pythonic(150)
benchmark_all_combinations_clike(150)
benchmark_fournums(150)


As you can see, I chose inside the benchmarking function the same statement that would cause all_combinations to terminate, and have no effect for the other combination functions.
When run with

python -m cProfile benchmark_combinations.py

the results include:

    2.817 benchmark_combinations.py:80(benchmark_itertools)
8.583 benchmark_combinations.py:84(benchmark_itertools_try)
126.980 benchmark_combinations.py:93(benchmark_itertools_equivalent)
46.635 benchmark_combinations.py:97(benchmark_itertools_equivalent_specialized)
44.032 benchmark_combinations.py:101(benchmark_all_combinations_pythonic)
18.049 benchmark_combinations.py:105(benchmark_all_combinations_clike)
10.923 benchmark_combinations.py:109(benchmark_fournums)


Lessons:

• Calling itertools.combinations_with_replacement is by far the fastest, taking about 2.7 seconds. It turns out that it’s written in C, so this would be hard to beat. (Still, writing it in a try block is seriously bad.)
• The “equivalent” Python code from the itertools documentation (benchmark_itertools_combinations_with_replacment) is about 50x slower.
• Gets slightly better when specialized to numbers.
• Simply generating all combinations without an upper bound is actually faster.
• It can be made even faster by writing it in a more C-like way.
• The tuples version with the loop unrolled manually is rather fast when seen in this light, less than 4x slower than the library version.

Written by S

Sun, 2015-02-08 at 00:03:38

Boolean blindness

(Just digesting the first page of Google search results.)

One of the lessons from functional programming is to encode as much information as possible into the types. Almost all programmers understand to some extent that types are helpful: they know not to store everything as void* (in C/C++) or as Object (in Java). They even know not to use say double for all numbers, or string for everything (as shell scripts / Tcl do). (This pejoratively called “stringly typed”.)

A corollary, from slide 19 here, is that (when your type system supports richer types) a boolean type is almost always the wrong choice, as it carries too little information.

The name “Boolean blindness” for this seems to have been coined by Dan Licata when taught a course at CMU as a PhD student.

There is no information carried by a Boolean beyond its value, and that’s the rub. As Conor McBride puts it, to make use of a Boolean you have to know its provenance so that you can know what it means.
[…]
Keeping track of this information (or attempting to recover it using any number of program analysis techniques) is notoriously difficult. The only thing you can do with a bit is to branch on it, and pretty soon you’re lost in a thicket of if-then-else’s, and you lose track of what’s what.
[…]

The problem is computing the bit in the first place. Having done so, you have blinded yourself by reducing the information you have at hand to a bit, and then trying to recover that information later by remembering the provenance of that bit. An illustrative example was considered in my article on equality:

fun plus x y = if x=Z then y else S(plus (pred x) y)

Here we’ve crushed the information we have about x down to one bit, then branched on it, then were forced to recover the information we lost to justify the call to pred, which typically cannot recover the fact that its argument is non-zero and must check for it to be sure. What a mess! Instead, we should write

 

fun plus x y = case x of Z => y | S(x') => S(plus x' y)
 

No Boolean necessary, and the code is improved as well! In particular, we obtain the predecessor en passant, and have no need to keep track of the provenance of any bit.

Some commenter there says

To the best of my knowledge, Ted Codd was the first to point out, in his relational model, that there is no place for Boolean data types in entity modeling. It is a basic design principle to avoid characterizing data in terms of Boolean values, since there is usually some other piece of information you are forgetting to model, and once you slam a Boolean into your overall data model, it becomes very hard to version towards a more exact model (information loss).

An example from Hacker News (on an unrelated post):

Basically, the idea is that when you branch on a conditional, information is gained. This information may be represented in the type system and used by the compiler to verify safety, or it can be ignored. If it is ignored, the language is said to have “boolean blindness”.
Example:


if (ptr == NULL) {
... a ...
} else {
... b ...
}


In branch a and branch b, different invariants about ptr hold. But the language/compiler are not verifying any of these invariants.
 

  data Maybe a = Nothing | Just a

 

This defines a type “Maybe”, parameterized by a type variable “a”, and it defines two “data constructors” that can make a Maybe value: “Nothing” which contains nothing, and “Just” which contains a value of type “a” inside it.
This is known as a “sum” type, because the possible values of the type are the sum of all data constructor values.
We could still use this sum data-type in a boolean-blind way:


if isJust mx then
.. use fromJust mx .. -- UNSAFE!
else
.. can't use content of mx ..


However, using pattern-matching, we can use it in a safe way. Assume “mx” is of type “Maybe a”:
 

  case mx of
Nothing -> ... There is no value of type "a" in our scope
Just x -> ... "x" of type "a" is now available in our scope!

 

So when we branch on the two possible cases for the “mx” type, we gain new type information that gets put into our scope.
“Maybe” is of course a simple example, but this is also applicable for any sum type at all.

Another from notes of someone called HXA7241:

A nullable pointer has two ‘parts’: null, and all-other-values. These can be got at with a simple if-else conditional: if p is not null then ... else ... end. And there is still nothing wrong with that. The problem arrives when you want to handle the parts – and you lack a good type system. What do you do with the non-null pointer value? You just have to put it back into a pointer again – a nullable pointer: which is what you started with. So where has what you did with the test been captured? Nowhere. When you handle that intended part elsewhere you have to do the test again and again.

A Reddit discussion: Don Stewart says

Not strongly typed, richly typed. Where evidence isn’t thrown away. Agda is about the closest thing to this we have.

Relation to “object-oriented programming”

There’s also a good (and unintentionally revealing) example there by user munificent. Consider Harper’s example, which in more explicit Haskell could be:


data Num = Zero | Succ Num

plus :: Num -> Num -> Num
plus Zero     y = y
plus (Succ x) y = Succ (plus x y)


We might write it in Java as the following:
 

interface Num {}
class Zero implements Num {}
class Succ implements Num {
public Succ(Num pred) {
this.pred = pred;
}
public final Num pred;
}

Num plus(Num x, Num y) {
if (x instanceof Succ) {      // (1)
Succ xAsSucc = (Succ)x;       // (2)
return new Succ(plus(xAsSucc.pred, y));
} else {
return y;
}
}

 

Here instanceof returns a boolean (comment (1)), but doesn’t carry with it any information about what that boolean represents (namely that x is an instance of Succ) so when we get to the next line (2) we’re forced to do an unsafe cast. As programmers, we know it’s safe from context, but the compiler doesn’t.

There is a way in Java of avoiding this situation (where the programmer has context the compiler doesn’t):


interface Num {
Num plus(Num other);
}

class Zero implements Num {
public Num plus(Num other) {
return other;
}
}

class Succ implements Num {
public Succ(Num pred) {
this.pred = pred;
}

public Num plus(Num other) {
return new Succ(pred.plus(y));
}

public final Num pred;
}


But see what has happened (by user aaronia):

There’s a rub though — in your first code snippet, “plus” was written as a non-member function; anyone can write it as a stand alone library. It was modular. But, as you demonstrated, it had the redundant type check.
However, your second code snippet has lost this modularity. You had to add new methods to the Num data type.

I think this is the pitfall of Object-Oriented Programming (which is like “Pants-Oriented Clothing”): objects can talk about themselves, but it’s harder to talk about objects.

If you want to write a function that does similar things for a bunch of types, you have to write similar function definitions in all those different classes. These function definitions do not stay together, so there is no way of knowing or ensuring that they are similar.

Written by S

Sat, 2015-01-31 at 14:55:00

Posted in computer science

Tagged with

C++ vs Java terminology glossary

E.g. there is no such thing as a “method” in C++. As far as the C++ standard is concerned, functions inside classes are always called “member functions”.

Here is a handout from this course (taught by, AFAICT, Jeffrey S. Leon) that helps me understand the Java people.

Written by S

Sat, 2015-01-31 at 11:53:06

Posted in programming

Tagged with

The “most natural” definition of the div and mod functions

with one comment

[incomplete: must add examples and more discussion]

Most programming languages include a “remainder” or “modulo” function, and also an integer division (“quotient”) function. Given two integers $D$ and $d$, let’s call the results of these functions $r$ and $q$ respectively.

For positive $D$ and $d$, it is clear what $q$ and $r$ should be: $q = \left\lfloor D/d \right\rfloor$ is the largest integer $n$ such that $nd \le D$, and $r = D - qd$ is the remainder which therefore satisfies $0 \le r < d$.

What should we do when, as frequently happens, $D$ is negative, or (as less frequently happens) $d$ is negative?

For negative $D$ and positive $d$, there are two choices when $D$ lies between two multiples of $d$ (i.e. $q_1 d < D < q_2 d$):

(1) Set $q$ to the lesser value, so that $0 \le r < d$ continues to hold, or
(2) Set $q$ to the greater (and therefore smaller in magnitude) value.

There are very good reasons why (1) is preferable to (2): it ensures that the function $a \bmod m$ is always positive no matter what the value of $a$, so that, for example, $a \equiv b \pmod m \iff (a \bmod m) = (b \bmod m)$.

And indeed that is what the more recent programming languages do. There is a table on Wikipedia: C, C++, Java, Go(!), OCaml(!), PHP, all have the “bad” behaviour, while Maple, Mathematica, Microsoft Excel, Perl, Python, Ruby have the “good” behaviour. Some languages have separate functions for both behaviours (e.g. Haskell has quotRem and divMod functions, similarly Common Lisp, Fortran, MATLAB).

There’s also the question of what to do when $d$ is negative, which turns out not to matter much (as long as it’s consistent with the above). One defintion is to continue to have $q$ be the lesser value, and the other is to continue to insist that $r \ge 0$. Both are fine, though sometimes the latter is nicer.

These are elaborated in The Euclidean Definition of the Functions div and mod by Raymond T. Boute, ACM Transactions on Programming Languages and Systems, Vol 14, No. 2, April 1992.

Written by S

Mon, 2015-01-12 at 09:30:35

Viṣṇu, appearing before Bali as Vāmana, transformed into Trivikrama, filling the universe, covering all the earth and the heavens in two steps.

The verse that opens the Pūrva-pīṭhikā of Daṇḍin’s Daśakumāracarita plays on this imagination, and on the word daṇda / daṇḍin. Here’s the verse (in Sragdharā metre of pattern GGGGLGG—LLLLLLG—GLGGLGG):

May the leg of Trivikrama,
pole for the parasol that is the universe,
stem of the lotus that is Brahma’s seat,
mast of the ship that is the earth,
rod of the streaming banner that is the river of the Gods,
axle-rod around which the zodiac turns,
pillar of victory over the three worlds,
rod of death for the enemies of the Gods,
favour you with blessings.

jyotiścakr’-âkṣa-daṇḍas tribhuvana-vijaya-stambha-daṇḍo ‘ṅghri-daṇḍaḥ
śreyas traivikramas te vitaratu vibudha-dveṣiṇāṃ kāla-daṇḍaḥ //


ब्रह्माण्डच्छत्रदण्डः शतधृतिभवनाम्भोरुहो नालदण्डः
क्षोणीनौकूपदण्डः क्षरदमरसरित्पट्टिकाकेतुदण्डः ।
ज्योतिश्चक्राक्षदण्डस्त्रिभुवनविजयस्तम्भदण्डोऽङ्घ्रिदण्डः
श्रेयस्त्रैविक्रमस्ते वितरतु विबुधद्वेषिणां कालदण्डः ॥



[The Mānasataraṃgiṇī-kāra, agreeing with Santillana and von Dechend the authors of Hamlet’s Mill, considers the “pole” or “axis” motif central to the conception of Vishnu (e.g. matsya‘s horn, Mount Meru as the rod on kūrma, nṛsiṃha from the pillar, etc.: see here), sees much more depth in this poem, and that Daṇḍin was remembering this old motif.]

The translation above is mildly modified from that of Isabelle Onians in her translation (“What Ten Young Men Did”) of the Daśa-kumāra-carita, published by the Clay Sanskrit Library:

Pole for the parasol-shell that is Brahma’s cosmic egg,
Stem for Brahma’s lotus seat,
Mast for the ship that is the earth,
Rod for the banner that is the rushing immortal river Ganges,
Axle rod for the rotating zodiac,
Pillar of victory over the three worlds—
May Vishnu’s leg favor you with blessings—
Staff that is the leg of him who as Trivikrama reclaimed those three worlds in three steps,
Rod of time, death itself, for the demon enemies of the gods.

Ryder, in his translation (“The Ten Princes”), takes some liberties and manages verse in couplets:

May everlasting joy be thine,
Conferred by Vishnu’s foot divine,

Which, when it trod the devils flat,
Became the staff of this and that:

The staff around which is unfurled,
The sunshade of the living world;

The flagstaff for the silken gleam
Of sacred Ganges’ deathless stream;

The mast of earth’s far-driven ship,
Round which the stars (as axis) dip;

The lotus stalk of Brahma’s shrine;
The fulcrumed staff of life divine.

For another verse that fully gets into this “filling the universe” spirit, see The dance of the bhairava on manasa-taramgini.

Written by S

Sun, 2014-08-17 at 23:36:42