Archive for March, 2009

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).

Problem 5 ver. 1: brute-force

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

What is the smallest number divisible by each of the numbers 1 to 20?

This is also quite known problem --- finding a least common multiple (LCM).

As usual, let's start with the brute-force solution.

  1.         (define (least-common-multiple-bruteforce divisors)
  2.            (define (iterate x) (if (all-divide? x divisors) x (iterate (+ x 1))))
  3.            (iterate (max-list divisors)))
  4. (define (solution-5-bruteforce n) (least-common-multiple-bruteforce (numbers 2 n)))

This is the most inefficient way we can invent for the task of finding LCM. The complexity in the worst case is something like O(p^n), when n divisors out there are prime numbers, each is p at the average (but different, of course, then their LCM is just their product). More strictly, the number of divisions is up to n*p^n in the worst case (would be that if not shorcutted logical operations in (all-divide?) function).

Don't install Linux onto /dev/sdc

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

I had three HDD drives, and I made a mistake installing Linux on the third one. I think, "the third" means that it hangs on SATA-channel 3. But GRUB sees a (first on that drive) boot partition at it as (hd0,0), if I choose the drive as the first to boot from in BIOS.

So, I removed one drive from a system, and my /dev/sdc became /dev/sdb. Of course, /etc/fstab still contains /dev/sdc* references and I get a kernel panic at boot. Actually, my GRUB also contains reference to the root partition at /dev/sdc, but this can be changed in interactive GRUB mode.

The issue can be solved changing /etc/fstab with a sytem rescue cd/usb, but I prefer to have no limitations on changing drives. I took a clean HDD, put it on SATA-channel 1 (it appears as /dev/sda), partitioned properly and copied everything from an old drive. Then edited /etc/fstab, grub-install --no-floppy /dev/sda with a proper grub.conf and it just works. Now I have two identical Linuxes on different drives, and I will probably keep the old one for a while (just in case).

By the way, at first I made a mistake copying with bare cp -r command. This made user accounts (except root) not usable, as access rights were changed. Copy with cp -a in this situation.

Problem 4 ver. 1: brute-force

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

Find the largest palindrome made from the product of two 3-digit numbers.

An additional function that filters out empty lists from a list of lists:

  1.         (define (filter-empty-lists lists) (filter (lambda (list) (not (null? list))) lists))

The function that represents a number in arbitrary number system and the function that returns 10-base digits for a number (starting from the rightmost digit):

  1.         (define (represent-in-radix n k) (if (= n 0) '() (cons (mod n k) (represent-in-radix (div n k) k))))
  2.          (define (digits n) (represent-in-radix n 10))

(digits) function could use standard (number->string), but this generalized solution I like more. Now a solution to the problem looks as easy as:

  1.         (define (palindrome-number? n) (let ([d (digits n)]) (equal? d (reverse d))))
  2.          (define (find-palindromes-among-products n) (map (lambda (x) (map (lambda (y) (* x y)) (numbers-filtered x n (lambda (y) (palindrome-number? (* x y)))))) (numbers 1 n)))
  3.  
  4. (define (solution-4-bruteforce n) (max-list (map max-list (filter-empty-lists (find-palindromes-among-products n)))))

Notice, for comparing lists we use (equal?), not (eq?) and not (eqv?) - they would return just #f. However, we could use (eq?) instead of (null?) in (filter-empty-lists) to compare a list to the empty one. As regards number of operations, we have n^2 / 2 multiplications, as many (palindrome-number?) calls that create digits lists (up to 6 divmod per each) and compare them (up to 6 comparisons per each). So, the complexity is O(n^2), and memory use is proportional to the palindrome numbers density in the n by n matrix (half of which we actually iterate over to find an answer).

Problem 3 ver. 1 and 2: brute-force and optimization

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

Problem 3

Find the largest prime factor of a composite number.

is a very well known problem called factorization. The fundamental theorem of arithmetics comes in handy.

Brute-force in this case is just iterating from 2 upwards, searching for factors:

  1.         (define (factorize-bruteforce n)
  2.            (define (iterate n x) (if (> x n) (list n) (if (divides? n x) (cons x (iterate (/ n x) x)) (iterate n (+ x 1)))))
  3.            (iterate n 2))

If a factor is found, we divide the number by it, and continue with searching factors of a quotient. We don't need to start from 2 again (see the theorem).

The complexity for finding one factor is O(n) in the worst case. Let us optimize at once, stopping the iteration at sqrt(n). Indeed, a number cannot have a factor greater than its square root. This improves the worst case complexity drastically to O(\sqrt(n)) and this is the classical factorization algo.

  1.         (define (factorize-sqrt-complexity n)
  2.            (define (iterate n x) (if (> x (sqrt n)) (list n) (if (divides? n x) (cons x (iterate (/ n x) x)) (iterate n (+ x 1)))))
  3.            (iterate n 2))

Now, having written additional function (max-list) for finding maximums through lists, we can solve the third problem:

  1.         (define (max-list list) (fold-left max (car list) list))        
  2. (define (solution-3-bruteforce n) (max-list (factorize-bruteforce n)))
  3. (define (solution-3-optimized-1 n) (max-list (factorize-sqrt-complexity n)))