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.

Saturday, December 27, 2014

Project Euler memo: Problem 449

Problem 449: Chocolate covered candy. Easier than I thought. 3 seconds in Python and 0.3 seconds in Golang.