Sunday, September 06, 2015

Project euler memo: Problem 510

Problem 510: Easy. 1.5 min in Golang.

Friday, August 14, 2015

Memory size with Golang

In the previous post, I complained on the slowness of Golang. It seems that it is because that I requested more memory than the machine has. In the following snippet, by default, 's' is zero-initialized and the program should print only the size of memory, in this case:

memory size is 4000000000

But if the length of array is 500*10^6, the program finds lots of non-zero elements. If the length is one tenth, i.e. 50*10^6, there is no problem. Since my machine is a Macbook air with 4GB DRAM, now I am thinking that Golang has some problem with memory size, but not very sure.

(Update 8/17/2015) This happens the array size is over 2GB.  There is a discussion here.

package main

import (

var s [500000000] int

func main () {
  mx := 500000000

  fmt.Println("memory size is", unsafe.Sizeof(s))
  for i:=0; i< mx; i+=1 {
    if s[i] != 0 {

Project euler memo: Problem 512

Problem 512: Counting the sum of Euler's totient. Basically I did brute-force. At first I tried to do it in  Golang, but it took forever to initialize a prime sieve. Then I did the same thing in C++ and it just takes 40 seconds. Up until 1/10 of the size, Golang does it fast enough.


Congratulations, the answer you gave to problem 512 is correct.
You are the 503rd person to have solved this problem.

Sunday, August 09, 2015

Project euler memo: problem 504

Problem 504:  Counting the number of lattice points in rectangles. It's been 7 months since last time I solved a problem. I chose the easiest problem by difficulty rate. Simple brute force in Python. 5 minutes.
(update 8/12)
I re-wrote it in Golang, including the suggestions in the forum. Now it runs in 1.2 seconds.

Saturday, April 25, 2015

Binary search on an array

I read a conference paper lately that has a pseudo code. In the code, there was a binary search and I noticed that the algorithm does not stop. That part in the paper is not very important but I myself confused at first, so I make it clear. 

I took a look at Knuth's TAOCP and I translated the description into Python:

# search key between [l,u]
# returns -1 on failure
def search1(key, arr):
  l = 0
  u = len(arr)-1

  while l<=u:
    m = (l+u)/2
    if arr[m] == key:
      return m
    elif arr[m] > key:
      u = m-1
      l = m+1
  return -1

This is simple and it has the case for failure.

What happens if the upper limit is an open end? I re-wrote it in this way.

# search key between [l,u)
# you need to be sure that you have an answer in arr
def search2(key,arr):
  l = 0
  u = len(arr)

  while l+1<u:
    m = (l+u)/2
    if arr[m] > key:
      u = m
      l = m
  return l

It does not have the case for failure so you need to be careful when you call it. There is a trick to compare l and u this case.

The algorithm in the paper is a mix of these and it does not stop. 

Sunday, January 25, 2015

Project Euler memo: Problem 443

Problem 443: GCD sequence. It's interesting and hard. I don't like it. One minute in Python.

Friday, January 23, 2015

Project Euler memo: Problem 497

Problem 497: Drunken Tower of Hanoi. Relatively easy. 24 minutes in Python.

Monday, January 12, 2015

Project Euler memo: Problem 435

Problem 435: Fibonacci coefficient  polynomials. Straightforward computation of Fibonacci numbers with a little trick on modulo inverse. Less than 0.1 seconds in Python.

Sunday, January 11, 2015

Project Euler memo: Problem 430

Problem 430: Flipping discs. A kind of brute force on N. 10 minutes in Golang. I need to learn in the forum later.

Saturday, January 10, 2015

Project Euler memo: Problem 269

Problem 269: One of the two problems left in the 200s. 3 seconds in Python.