kdb programming challenge – number bases

Blog kdb+ 2 Oct 2014

Matt Doherty

In systems of numbers the radix or base is the number of unique digits or symbols that are used to represent numbers. By far the most well known and widely used is the decimal system, which uses the ten digits from 0 through 9 (largely because – much to William Shatner’s surprise – we have 10 fingers).

My. Only intention. In. Speaking this way. Is. To. Make absolutely sure. That. You! The listening audience. Are. Able to. Hear my words! Clearly.

Some other handy bases include binary (radix of 2) since it’s the language most computers speak, and sexagesimal (radix of 60) which is used for time and circular coordinates because 60 is very divisible.

So, the challenge this time is to write a base number converter that accepts any positive integer (in base 10, like normal) and a base to convert to as the two arguments, and returns a list which is the digits of the number in the new base. The digits themselves can be in base 10, no need to start using “A-F” etc. The answer should never return zeros at the start; we don’t typically write two as 000002.

So for example some numbers in binary:

q) f[15;2]
1 1 1 1
q) f[16;2]
1 0 0 0 0

Or in some other bases:

q) f[123;6]
3 2 3
q) f[123;7]
2 3 4
q) f[123456;60]
34 17 36

This problem will be the first in a short series involving number bases and some hopefully interesting related topics.

[showhide type=”post” more_text=”Show Solution” less_text=”Solution” hidden=”yes”]

There’s definitely more than one nice solution to this problem, so I’ll show you two of the best from our office. The first (courtesy of Kent Lee) makes very nice use of recursion to divide by successively bigger powers of the radix until we can’t divide any further:

f:{$[x<y;(),x;.z.s[x div y;y],x mod y]}

The second (straight from the mind of Andrew Steele), takes a different approach and makes very clever use of iterate to solve the problem:

f:{1_reverse div[;y]\[x]mod y}

This one also wins the “who can use the least characters” competition, despite the inclusion of reverse! Very impressive. I’m sure there are other nice ways to do this too, as always feel free to post your answers in the comments!

Remember – you can’t beam through a forcefield, so don’t try it.


Share this: