## 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 (
"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.