Happy New Year!

I was not supposed to have any New Year’s resolutions since they usually don’t work but… I haven’t been paying much attention to the blog for quite some time (mea culpa!) and it is high time to bring some more life here. So my mid-January resolution is: post some new stuff!

And a Happy, column-oriented New Year!

quicksort in q

Something Attila showed during the recent London kx meetup:


q:{$[2>distinct x;x;raze q each x where each not scan x < rand x]}

Short and sweet implementation of quicksort. It is slower than q built-ins but obviously it is hard to beat q…

If you are wondering why he didn’t use .z.s for recursion, the answer is very simple – he was aiming for the shortest implementation.

Tagged

Let’s Meetup in London – Nov 19th

As some of you may know, few moths ago a kx London meetup group was started and now it is organizing another event on November 19th. Taking into account that speakers include Simon Garland from kx and Attila Vrabecz from QuantumKDB, the evening looks promising.

Tagged

Karatsuba Multiplication

Karatsuba algorithm is a fast multiplication algorithm which is significantly faster then the good old classical algorithm we know from school. For example to compute product of two 1024-digit numbers, we normally need around 1,000,000 single-digit multiplications. With Karatsuba algorithm that number drops to around 59k.

In short it provides a formula that allows us to compute product of two large numbers using three multiplications of three smaller numbers, some additions and digit shifts.  Implementing it in q will hide the whole awesomeness from us since q is too fast and too furious. But it still can be a nice exercise to play around with lists etc.

So here is my one-liner:


karatsuba:{[x;y]
wsum[(xexp[10;n]-c;1-c;c);prd each (d;m;d+m:(x;y)-c*d:(x;y) div c:10 xexp (n:max count each string abs (x;y))%2)]}

Any shorter, faster, more clever approaches?

Tagged ,

FD Lecture Series

FD has published so far four q for Gods lectures covering .e.g. kdb+ data management, storage and access methodology.

Tagged , , ,

P38: Compare the two methods of calculating Euler’s totient function

L-99 is a list of Prolog challenges with solutions in Lisp. However, the solutions you can find here are written in q.

Use the solutions of problems P34 and P37 to compare the algorithms. Take the number of logical inferences as a measure for efficiency. Try to calculate phi(10090) as an example.

P34 vs. P37
It seems that totientPhi2 is faster (avg. time = 0.1 ms):

\t do[10;totientPhi 10090]
6
\t do[10;totientPhi2 10090]
1

Tagged ,

P37: Calculate Euler’s totient function phi(m) (improved)

L-99 is a list of Prolog challenges with solutions in Lisp. However, the solutions you can find here are written in q.

See problem P34 for the definition of Euler’s totient function.

If the list of the prime factors of a number m is known in the form of problem P36 then the function phi(m) can be efficiently calculated as follows: let ((p1 m1) (p2 m2) (p3 m3) …) be the list of prime factors (and their multiplicities) of a given number m. Then phi(m) can be calculated with the following formula:

phi(m) = [(p1 - 1) * p1 ** (m1 - 1)] * [(p2 - 1) * p2 ** (m2 - 1)] * ...

Note that a ** b stands for the b’th power of a.

qSolution

Using primeFactorsMult the solution is rather easy:

totientPhi2:{[n]
  if[n=1;:n];
  mult:primeFactorsMult n;
  :`int$(*/)(mult[;0]-1)*mult[;0] xexp mult[;1]-1;
  };

Example
totientPhi2 each 1+til 15
1 1 2 2 4 2 6 4 6 4 10 4 12 4 8

Tagged , , ,

Kamil’s blog

Another q blog is here! Kamil’s blog has been started four months ago and you can find there some code snippets as well as q brush for SyntaxHighlighter.

Tagged , ,

P36: Determine the prime factors of a given positive integer (2)

L-99 is a list of Prolog challenges with solutions in Lisp. However, the solutions you can find here are written in q.

Construct a list containing the prime factors and their multiplicity.

Example
* (prime-factors-mult 315)
((3 2) (5 1) (7 1))

Hint: The problem is similar to problem P13.

qSolution

Looking at the above example we can notice that this problem is more similar to P10 because of factors with singular multiplicity. If it was similar to P13, than the grouping should look like:

* (prime-factors-mult 315)
((3 2) 5 7)

The current problem differs from P10 because of the order of elements in each sublist. In P10 we were assuming that the output consist of pairs (multiplicity; element). Now it is the other way around.

The solution is very simple as we can use functions defined in P10 and P35:

primeFactorsMult:{[x]
  :reverse each encode primeFactors x;
  };

Example
primeFactorsMult 5
5 1

primeFactorsMult 315
3 2
5 1
7 1

Tagged , , ,

P35: Determine the prime factors of a given positive integer

L-99 is a list of Prolog challenges with solutions in Lisp. However, the solutions you can find here are written in q.

Construct a flat list containing the prime factors in ascending order.

Example
* (prime-factors 315)
(3 3 5 7)

qSolution

The solution (primeFactors) is using isPrime function to determine if the number is primary or not. Integer factorization (pfact) is then run only for non-primary numbers.


pfact:{[n;d]
  if[any(n=1;isPrime n);:(),n];
  $[0=n mod pf:first d;:pf,.z.s[`int$n%pf;d];:.z.s[n;1_d];];
  };


primeFactors:{[n]
  if[n<1;'"rank"];
  :pfact[n;2+til floor sqrt n];
  };

Example
primeFactors 315
3 3 5 7

primeFactors 97
97

Tagged , , ,