How to remove "Please wait while the document is being prepared for reading" message in Acrobat

May 30th, 2009 by Ivan Lakhturov | 0 | Category: Programming | Tags: |

It really bothered me. So, I googled. All links give the same solution: one, two, three.

Problem 3: a note

May 5th, 2009 by Ivan Lakhturov | 0 | Category: Programming | Tags:

Find the largest prime factor of a composite number.

The problem of integer factorization is one of the most important in the number theory. Last time I implemented a classical algorithm with O(\sqrt{n}) complexity. The author of the Project Euler website suggests a small improvement --- iterating over only odd numbers, but I consider this as too tiny thing to do.

As regards the problem of factorization, I'd rather look in special literature, what are the known approaches (and I'll do that later, let's switch to the next one).

Problem 2 ver. 2, 3, 4: logarithmic complexity

April 17th, 2009 by Ivan Lakhturov | 0 | Category: Programming | Tags: |

Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million

The last time we had the straightforward O(n) solution: building a sequence, filtering out even values and adding them. We can improve a bit, noticing that actually, every third member of the Fibonacci sequence is even. We don't check then for evennes, but just jump over three components each time. This version 2 (I don't publish it here) should be several times faster, but still is O(n) in performance.

We can also express a member of the Fibonacci sequence via the third and sixth members from behind: F_{n} = 4 F_{n-3} + F_{n-6} and compute those values as the values of a new sequence: E_n = 4 E_{n-1} + E_{n-2}. This version 3 is essentially the same as the previous one and again, I don't publish it here.

The drastic improvement is obtained using the expression \sum_{k=0}^{n} F_{3k} = \frac{F_{3n+2}-1}{2} (I've added it and a proof to the wikipedia article, but they immediately reverted my changes as "unsourced" --- this is pathetic). Now the sum is obtained just computing one Fibonacci member, and this can be done with O(log n).

Indeed, we can compute a Fibonacci member exponentiating the appropriate matrix, and this exponentiation, just like usual one, can be done with O(log n). I prefer this solution over using the golden ratio exponentiation formula (again logarithmic complexity), because only integer-operations are involved. So, this is the version 4 of the solution.

  1.         (define (fibonacci-member-logarithmic n) (matrix-2d-a12 (^-2d fibonacci-matrix n)))
  2.          (define (fibonacci-sum-even n) (/ (- (fibonacci-member-logarithmic (+ n 2)) 1) 2))

I quickly outlined a class for 2D matrices and operations with it:

  1.         (define-record-type matrix-2d (fields a11 a12 a21 a22))
  2.          (define identity-matrix-2d (make-matrix-2d 1 0 0 1))
  3.          (define fibonacci-matrix (make-matrix-2d 1 1 1 0))
  4.          (define (*-2d A B) (let ([a11 (matrix-2d-a11 A)]
  5.                                   [a12 (matrix-2d-a12 A)]
  6.                                   [a21 (matrix-2d-a21 A)]
  7.                                   [a22 (matrix-2d-a22 A)]
  8.                                   [b11 (matrix-2d-a11 B)]
  9.                                   [b12 (matrix-2d-a12 B)]
  10.                                   [b21 (matrix-2d-a21 B)]
  11.                                   [b22 (matrix-2d-a22 B)])
  12.                               (make-matrix-2d (+ (* a11 b11) (* a12 b21)) (+ (* a11 b12) (* a12 b22))
  13.                                               (+ (* a21 b11) (* a22 b21)) (+ (* a21 b12) (* a22 b22)))))
  14.          (define (^-2d-linear A n) (apply-n-times identity-matrix-2d n (lambda (x) (*-2d x A))))
  15.          (define (^-2d-logarithmic A n) (if (= n 0) identity-matrix-2d
  16.                                             (if (odd? n) (*-2d A (^-2d-logarithmic A (- n 1)))
  17.                                                 (let ([B (^-2d-logarithmic A (div n 2))]) (*-2d B B)))))
  18.          (define ^-2d ^-2d-logarithmic)

The solution is O(1) in memory and O(log n) in performance - of course, where n denotes the index of a number in the Fibonacci sequence. And we have been questioned about the cutset, where members of a sequence are less than certain number. Then an additional function (closest-fibonacci-index) comes in handy (see the wiki for explanation):

  1.         (define golden-ratio (/ (+ 1 (sqrt 5)) 2))
  2.          (define (closest-fibonacci-index f) (round (log (* f (sqrt 5)) golden-ratio)))
  3. (define (solution-2-optimized-3 n) (fibonacci-sum-even (closest-fibonacci-index n)))

The final touch is asking ourselves about complexity of the (log) function. Well, it can be computed fast enough not to spoil complexity of the algo's main part.

Problem 1 ver. 3: optimization

April 5th, 2009 by Ivan Lakhturov | 0 | Category: Programming | Tags: |

Find the sum of all the multiples of 3 or 5 below 1000.

Let us generalize again to a finite set of factors.

There is a formula for the power of finite sets

|A \bigcup B| = |A| + |B| - |A \bigcap B|

which can be generalized to a finite number of finite sets

p(\bigcup\limits_i^n A_i) = \sum\limits_{i_1} p(A_{i_1}) - \sum\limits_{i_1,i_2} p(A_{i_1} \bigcap A_{i_2}) + \sum\limits_{i_1,i_2,i_3} p(A_{i_1} \bigcap A_{i_2} \bigcap A_{i_3}) - ... + (-1)^{n-1} p(\bigcap\limits_i^n A_i)

or in a somewhat less understandable, but concise notation

p(\bigcup\limits_i^n A_i) = \sum\limits_{\alpha \in 2^{\mathbb{N}_n}} (-1)^{|\alpha|-1} p(\bigcap\limits_{j \in \alpha} A_j)

Here p(...) is a measure (i.e. it commutes with the union sign) and can be replaced with |...| --- power of a set sign or, if we are in the natural numbers space, with the sum of elements sign, as in our case. \alpha is not a multiindex, but a subset of the natural numbers cut from 1 to n.

Now by \bigcup_{i=1}^n A_i we denote the set of all the multiples of factors f_i, less than certain number N, where i varies from 1 to n (each A_i is respectively the set of multiples of a factor f_i). We use the above-mentioned formula to compute the measure of the union \bigcup_{i=1}^n A_i via measures of all A_i and measures of all finite intersections of them.

Suppose, we have a number a, prime or not, and the set of all it's multiples A (they include only numbers less than N). Power of this set is of course N \div a (div operation) and the sum of its members can be calculated by the well-known formula for the sum of an arithmetic progression.

As regards all the intersections, it is understandable that we ought to calculate the least common multiple (LCM) of taken factors, and the set-intersection of their multiples will be just a set of its multiples. However, the current version of the solution assumes that we take primes as factors, then the LCM of them is just their product. When I calculate proper LCM in Problem 5 (up to now there is a bruteforce version), I will switch the temp version to it.

Let's see the solution. New util functions:

  1. (define (mul-list list) (fold-left * 1 list))
  2. (define (^ base power) (expt base power))
  3. (define (sum-arithmetic-progression first step n) (/ (* n (+ (* 2 first) (* step (- n 1)))) 2))

The function that calculates subsets of a set:

  1. (define (subsets set)
  2.   (define (recursion set rest) (if (null? set) (list rest)
  3.                                    (let ([head (car set)] [tail (cdr set)])
  4.                                      (append (recursion tail rest) (recursion tail (cons head rest))))))
  5.   (recursion set '()))

Important thing about this function is that it returns the empty set as the first element and the full set as the last element of a result list, all other subsets are in between. The number of subsets of a finite subset is just 2^n, so the complexity is O(2^n) --- it would be better visible with an imperative-iterative version of this function (I'm not posting it here). As regards memory, the function generates all the subsets as lists which in whole contain \sum_{k=1}^n k C^n_k = n 2^{n-1} elements (strange, this neat formula isn't on Wikipedia yet, I should add it there), that is the memory load is O(n 2^n). This is a not-so-good idea to load everything into memory, as we can rewrite this function (and the function that is down here in the post) iteratively with O(n) memory complexity --- taking advantage of combinadics, but for now I am satisfied enough with this version.

Using the formula above the solution now as simple as

  1. (define (sum-multiples-less-than n divisors)
  2.   (define (sum-of-one factor) (sum-arithmetic-progression factor factor (div n factor)))
  3.   (define (lcm-temp factors) (if (null? factors) 0 (mul-list factors)))
  4.   (define (measure subset) (* (^ (- 1) (+ (length subset) 1)) (sum-of-one (lcm-temp subset))))
  5.   (sum-list (map measure (cdr (subsets divisors)))))

With that (cdr) I cut off the empty subset, whose measure is zero (otherwise the (sum-of-one) function has to be a bit more complex).

Let's be careful with notation: n here is actually not the same n, as in the (subsets) function, but the number N up there, the maximum of our multiples-sets. The performance complexity depends on k and N, but we are interested only in complexity, depending on N. Let's assume that k is small comparing to N, which should be the usual case. Then the complexity is roughly speaking O(1), doesn't depend on N, as we wanted (I remind that in the previous version we had O(N) complexity).

The final touches are the regression tests:

  1. (assert (=
  2.          (sum-list (multiples-less-than-bruteforce 10 '(3 5)))
  3.          (sum-multiples-less-than 10 '(3 5))))
  4. (assert (=
  5.          (sum-list (multiples-less-than-bruteforce 1000 '(3 5)))
  6.          (sum-multiples-less-than 1000 '(3 5))))
  7. (assert (=
  8.          (sum-list (multiples-less-than-bruteforce 10000 '(3 5 7 19)))
  9.          (sum-multiples-less-than 10000 '(3 5 7 19))))
  10. ;(assert (=
  11. ;        (sum-list (multiples-less-than-bruteforce 1000 '(3 5 15)))
  12. ;       (sum-multiples-less-than 1000 '(3 5 15))))

The last commented one breaks, of course, as 15 is not prime - the LCM algo should be updated still.

Basic laptop maintenance

March 31st, 2009 by Ivan Lakhturov | 0 | Category: Miscellaneous | Tags: |

Some months ago my notebook began to overheat. When the CPU is loaded enough, its temperature grows over 95 degrees Celsius, and a guard mechanism throttles down its frequency to 40 % and waits until it cools down. Within a few minutes the system is badly responsive.

I bought a cooling platform for it, but with time it couldn't restrain the heat. A problem became worse and worse, but the warranty for the laptop was void already. So, I took a screwdriver and solved it:

A dense layer of dust covered the radiator and prevented air flow. Now under 100 % load my CPU is cool enough. I mean, for a Turion --- 80 degrees Celsius for the general sensor, 85 for the first core, and 91-93 for the second one (sitting on a table, without a cooling platform). Strange gradient, but anyway, a system doesn't freeze now.

Learned a bit about PLT-Scheme

March 20th, 2009 by Ivan Lakhturov | 0 | Category: Programming | Tags:

I've looked through the Quick: An Introduction to PLT Scheme with Pictures document. And what I've learned is:

  • There is a library (#lang slideshow) embedded into PLT-Scheme, which provides some easy-to-use graphic primitives and a GUI library (scheme/gui/base). The first can be used for drawing on GUI's canvases.
  • There is an OOP library (scheme/class). I should look what's the backbone later.
  • PLT has the distribution system for libraries. The first eval of (require (planet something)) downloads from the PLaneT server and caches 'something' locally.

The last is quite nice, I should run through that server and look which libraries are actually implemented.

How to pivot (rotate a desktop from landscape to portrait)

March 11th, 2009 by Ivan Lakhturov | 0 | Category: Linux | Tags: |

Monitors become wider and wider due to the entertainment industry, but changing proportion in fact decreases a number of pixels from top to bottom of a screen. If you look at some program code now, you see just some lines clustered along the left boundary of a screen and lots of free space.

A standard coder should not appreciate that, unless he is me and likes spaghetti code style (by this I mean lines 200 symbols wide). However, this is applicable only for code in the functional paradigm. In the imperative style I don't do this. And anyway, there are usually code style conventions limiting that for a project.

I've seen some people using two source code windows filled with different source files. This could be nice, especially for diffs. However, I think, a coder should appreciate increasing number of lines vertically. The ultimate solution is to buy a monitor with the pivot function --- switching between landscape and portrait on-the-fly. Of course, this requires support from drivers/OS. And nvidia, radeon drivers provide that.

Switching under Windows is easy, for Linux it required some investigations. You enable it first in /etc/X11/xorg.conf (Section "Screen"):
Option "RandRRotation" "true"
This is for nvidia card, but I guess, radeon drivers should provide the same. Then under KDE you run a command:
xrandr -o left
to switch to the portrait mode or "-o normal" for switching back.

I also tried krandrtray application, but it didn't work for me. By the way, don't logout from KDE during the portrait mode. I filed a bug for the KDE team.

Installed LaTeX plugin for WordPress

March 8th, 2009 by Ivan Lakhturov | 0 | Category: Miscellaneous | Tags: |

I tried wpmathpub plugin, but it didn't work for me. Now thanks to Craig Rose I have a better plugin for math notation. It uses an external service (usually WordPress server) for turning LaTeX-notation into pics, and thus capable of much more than wpmathpub plugin (that uses the PhpMathPublisher library and implements just a small subset of TeX-formulae).

\tanh x =  \frac{\sinh x}{\cosh x} = \frac {\frac {e^x - e^{-x}} {2}} {\frac {e^x + e^{-x}} {2}} = \frac {e^x - e^{-x}} {e^x + e^{-x}} = \frac{e^{2x} - 1} {e^{2x} + 1} = -i \tan ix

Now with math notation possible to post here I will think up and publish some optimizations for Project Euler problems.

Problem 7 ver. 1 and 2: bruteforce and optimization

March 8th, 2009 by Ivan Lakhturov | 0 | Category: Programming | Tags: |

Find the 10001st prime.

The problem of finding primes is the most famous computational task in the number theory.

At first, let's update the (generate-list-iteratively) function. It now includes i - the parameter, which denotes number of eligible elements up to this moment. We use it in the stopping condition.

  1.         (define (generate-list-iteratively seed filter map step stop)
  2.            (define (iterate current i) (if (stop current i) '()
  3.                                            (let* ([ok (filter current)] [next (if ok (+ i 1) i)] [rest (iterate (step current) next)])
  4.                                              (if ok (cons (map current) rest) rest))))
  5.            (iterate seed 0))

Dependant functions are rewritten also. I refactored the factorization functions and added primality tests (usual straightforward ones):

  1.         (define (minimal-factor-bruteforce n)
  2.            (define (iterate n x) (if (> x n) n (if (divides? n x) x (iterate n (+ x 1)))))
  3.            (iterate n 2))
  4.          (define (minimal-factor-sqrt-complexity n)
  5.            (define (iterate n x) (if (> x (sqrt n)) n (if (divides? n x) x (iterate n (+ x 1)))))
  6.            (iterate n 2))
  7.          (define (factorize n minimal-factor) (let ([p (minimal-factor n)]) (if (= p n) (list p) (cons p (factorize (/ n p) minimal-factor)))))
  8.          (define (prime?-bruteforce n) (= (minimal-factor-bruteforce n) n))
  9.          (define (prime?-sqrt-complexity n) (= (minimal-factor-sqrt-complexity n) n))
  10.          (define (primes-list n prime?) (generate-list-iteratively 2 prime? (lambda (x) x) (lambda (x) (+ x 1)) (lambda (x i) (= i n))))

Now, having an extra function that returns the last element in a list, we can easily solve the 7-th problem:

  1.         (define (last list) (if (null? (cdr list)) (car list) (last (cdr list))))
  2. (define (solution-7-bruteforce n) (last (primes-list n prime?-bruteforce)))
  3. (define (solution-7-optimized-1 n) (last (primes-list n prime?-sqrt-complexity)))

The complexity in memory is O(n), as we store n primes. It could be O(1), of course, but I prefer this way for now. The performance complexity of the algorithm is hard to determine. Probably, I need to overlook some literature for that.

Problem 6 ver. 1: brute-force

March 6th, 2009 by Ivan Lakhturov | 0 | Category: Programming | Tags: |

What is the difference between the sum of the squares and the square of the sums?

No problems with brute-force here.

  1.         (define (square n) (* n n))
  2. (define (solution-6-bruteforce n) (let ([ns (numbers 1 n)]) (- (square (sum-list ns)) (sum-list (map square ns)))))

The number of operations (additions and multiplications) here is 3*n + 2. The complexity is O(n), and the algo is O(n) in memory as well (of course, can be done with O(1) in memory).