Problem 510: Easy. 1.5 min in Golang.

## Sunday, September 06, 2015

## 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 ( "fmt" "unsafe" ) 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 { fmt.Println(i) } } }

### 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 else: 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 else: 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.