Forem: msh2050

Increase function speed to get Fibonacci numbers in Golang

msh2050 — Fri, 15 Jul 2022 23:41:31 +0000

As a learning task, I start to search and try to improve functions speed to get Fibonacci numbers.

Fibonacci's numbers are a sequence of whole numbers arranged as:-

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

so the first thing dig into my mind is to try iteration methods:

    package main

    import "fmt"

    func fibonacci(n int) int {
        fn := make(map[int]int)
        fn[0] = 0
        fn[1] = 1

        for i := 2; i <= n; i++ {
            var f = 0
            f = fn[i-1] + fn[i-2]
            fn[i] = f
        }
        return fn[n]
    }

This is an easy function to calculate fn "Fibonacci" number starting from 0,1 and then one over the other up to fn(i).

it uses an easy method :

Fn = Fn-1 + Fn-2

where,

n > 1

The downside of this function is that it can calculate up to the fn(92) which is 7540113804746346429, after that number the result will be above the limit of an int value.

So the solution is to use "math/big" package.

func fibonacci(n int) *big.Int {
    fn := make(map[int]*big.Int)
    fn[0] = big.NewInt(0)
    fn[1] = big.NewInt(1)

    for i := 2; i <= n; i++ {
        var f = big.NewInt(0)
        f = f.Add(fn[i-1], fn[i-2])
        fn[i] = f
    }
    return fn[n]
}

with the above function you can get the fn(1000) which will be :

43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

the downside of the above function is that it will be very slow if you increase the number, my pc froze when trying to calculate fn(1e6).

Fortunately, there is a better method known as fast doubling I will not go deep to describe this method, you can check this article for more details although it is written for c++

we can implement the fast doubling as follows:

    func fibonaccibinary(n int) *big.Int {
        if n == 0 {
            return big.NewInt(0)
        }
        num := uint(n)
        mask := bits.RotateLeft(1, bits.Len(num)-1)
        a, b := big.NewInt(0), big.NewInt(1)

        for mask > 0 {

            c := Mul(a, Sub(Mul(b, big.NewInt(2)), a))

            d := Add(Mul(a, a), Mul(b, b))
            a = c
            b = d

            if num&mask > 0 {
                a, b = b, Add(a, b)

            }

            mask /= 2

        }

        return a
    }

if you want to further speed up the function we can change mask /=2 to mask >>= 1 and the method of calculating the mask (mask := bits.RotateLeft(1, bits.Len(num)-1)) is much faster than the one suggested in the mentioned article:

//slower than mask := bits.RotateLeft(1, bits.Len(num)-1)
func getmask(n int) int {

    h := 0
    for i := n; i > 0; i >>= 1 {
        h++
    }
    mask := 1 << (h - 1)

    return mask
}

I have to mention that using :

mask = bits.RotateLeft(mask, -1)

is faster than( mask >>= 1 ) but we should be careful that

    //if mask = 1
    bits.RotateLeft(mask, -1) != mask  >>= 1

If we review the last function there are two calculations that take significant time:

c := Mul(a, Sub(Mul(b, big.NewInt(2)), a))

d := Add(Mul(a, a), Mul(b, b))

so it is better to use what Golang shine in (goroutine) to make these calculation happen concurrently.
Also, we are calculating fn(i+1) in the last loop iteration.
so to implement these enhancements we can go for:-

func fibonaccichanggoroutin(n uint) *big.Int {
    if n == 0 {
        return big.NewInt(0)
    }

    // num := uint(n)
    chA := make(chan *big.Int)
    chB := make(chan *big.Int)
    a, b := big.NewInt(0), big.NewInt(1)

    // There is only one `1` in the bits of `mask`. The `1`'s position is same as
    // the highest bit of n(mask = 2^(h-1) at first), and it will be shifted right
    // iteratively to do `AND` operation with `n` to check `n_j` is odd or even,
    // where n_j is defined below.
    mask := bits.RotateLeft(1, bits.Len(uint(n)-1))
    for {

        if mask == 1 {
            // we are on last iteration wee need to just calculate a
            if n&mask > 0 { // n_j is odd: k = (n_j-1)/2 => n_j = 2k + 1

                a = Add(Mul(a, a), Mul(b, b))

            } else { // n_j is even: k = n_j/2 => n_j = 2k

                a = Mul(a, Sub(Mul(b, big.NewInt(2)), a))

            }
            return a

        }

        go CalA(a, b, chA)
        go CalB(a, b, chB)

        if n&mask > 0 { // n_j is odd: k = (n_j-1)/2 => n_j = 2k + 1

            a = <-chB
            b = Add(a, <-chA)
        } else { // n_j is even: k = n_j/2 => n_j = 2k

            a = <-chA
            b = <-chB
        }

        mask = bits.RotateLeft(mask, -1)
    }

}
func CalA(a, b *big.Int, ch chan *big.Int) {

    ch <- Mul(a, Sub(Mul(b, big.NewInt(2)), a))
}

func CalB(a, b *big.Int, ch chan *big.Int) {
    ch <- Add(Mul(a, a), Mul(b, b))
}

Finally you can check this repo for tests and benchmarks. the last function in this repo (func14) uses a table of precalculated Fibonacci numbers to speed up things...

Quickly create K3s cluster and add K3s nodes with GUI Tool using AutoK3s (Installation guide in WSL)

msh2050 — Sun, 10 Jul 2022 22:12:30 +0000

AutoK3s is a new tool that will make it easy to install and manage Kubernetes clusters in many platforms.
In this tutorial, we will install Kubernetes in windows WSL with the use of:-

Ubuntu 22.04 WSL distro

What is amazing in this distro is that they have built in systemctl. If you chose another distro, you should use other methods to make docker and other services start.

Docker for Linux (without docker desktop)

As you may know, docker desktop is not free anymore, and I found it use more resources from the pc.

K3s is a highly available, certified Kubernetes distribution designed for production workloads. The most important it is "Lightweight Kubernetes"

K3d is a lightweight wrapper to run k3s in docker.

AutoK3s

AutoK3s is a lightweight tool for simplifying K3s cluster management.

Install a Linux distro

it is recommended to use Ubuntu 22.04 in this tutorial. You can download it from Microsoft store.

It is advisable to upgrade.

sudo apt update && sudo apt upgrade

Enable systemctl

in your WSL edit /etc/wsl.conf

sudo nano /etc/wsl.conf

add the following line:

[boot]
command="/usr/libexec/wsl-systemd"

then close the terminal and restart WSL with the following command in your PowerShell

 wsl --shutdown

then you can start new WSL shell and check that systemctl is working

 ps aux

note that first line(PID 1) is systemctl

then check systemctl status:

systemctl status

for me, I got 3 failed services:

ssh.service
systemd-remount-fs.service
systemd-sysusers.service

to solve ssh service :

 apt-get install openssh-server openssh-client
 dpkg-reconfigure openssh-server

for the rest:

comment out the line in the /etc/fstab:

#LABEL=cloudimg-rootfs   /        ext4   discard,errors=remount-ro       0 1

open /usr/lib/systemd/system/systemd-sysusers.service and delete all lines, then add:

[Unit]
Description=Create System Users
Documentation=man:sysusers.d(5) man:systemd-sysusers.service(8)
DefaultDependencies=no
Conflicts=shutdown.target
After=systemd-remount-fs.service
Before=sysinit.target shutdown.target systemd-update-done.service
ConditionNeedsUpdate=/etc

[Service]
Type=oneshot
RemainAfterExit=yes
ExecStart=systemd-sysusers
TimeoutSec=90

[Service]
LoadCredential=

Finally, restart and check the services again.

Install Docker

the instructions for installing Docker in details from this tutorial, we can skip Sharing dockerd and adding script (because we use systemctl) in short this can be done with the following:

Install dependencies

sudo apt install --no-install-recommends apt-transport-https ca-certificates curl gnupg2

Switch to legacy iptables

update-alternatives --config iptables

select iptables-legacy

package repository configuration

First, temporarily set some OS-specific variables:

. /etc/os-release

Then, make sure that apt will trust the repo:

curl -fsSL https://download.docker.com/linux/${ID}/gpg | sudo tee /etc/apt/trusted.gpg.d/docker.asc

Then add and update the repo information so that apt will use it in the future:

echo "deb [arch=amd64] https://download.docker.com/linux/${ID} ${VERSION_CODENAME} stable" | sudo tee /etc/apt/sources.list.d/docker.list
sudo apt update

Install Docker

sudo apt install docker-ce docker-ce-cli containerd.io

Add user to Docker group

sudo usermod -aG docker $USER

Finally, close that WSL window, and launch WSL again. And check if docker is working:

 docker run --rm hello-world

Install K3D and AutoK3s

Install K3D

curl -s https://raw.githubusercontent.com/k3d-io/k3d/main/install.sh | bash

Install AutoK3s Download the binary from the release page.

curl https://github.com/cnrancher/autok3s/releases/download/v0.5.1/autok3s_linux_amd64 --create-dirs -o ~/bin/autok3s

Make it executable

chmod 755 ~/bin/autok3s

then add to path

echo 'export PATH="$HOME/bin:$PATH"' >> ~/.bashrc

install kube-explorer (optional)

curl https://github.com/cnrancher/kube-explorer/releases/download/v0.2.9/kube-explorer-linux-amd64 --create-dirs -o ~/bin/kube-explorer

chmod 755 $HOME/bin/kube-explorer

start `autok3s` to deploy Kubernetes cluster

autok3s serve

Open 127.0.0.1:8080 on your browser to start create, delete modify Kubernetes clusters.

Select k3d as provide and give name to the cluster and specify how many mater/worker nodes you want.

This is a sample option I used to build a cluster with one master node and one worker node and limit their ram usage to 1 GB

You can add the explorer to the cluster

Install minikube with podman and CRI-O on wsl2 / Windows 11

msh2050 — Tue, 05 Jul 2022 01:09:14 +0000

What is minikube

There are various solutions that can deploy Kubernetes on your development machine, minikube as it is advertised on their site quickly sets up a local Kubernetes cluster on macOS, Linux, and Windows.
The easy setup can be done if you want the standard method using virtual machine or docker, but if you want to try the newcomers podman and CRI-O it will be tricky and may not work as it is experimental.
In this tutorial, I will share the steps that I make it working in a successful and easy way.

Install WSL distro

I used Distrod tool to install WSL that has extra features like systemd, auto-start and port forwarding ability.

1. Download Distrod zip file from the release page.

2. Extract the file and just double click to run the tool

3. Select `[2] Download an image from linuxcontainers.org`

I tried Ubuntu, but it is not easy to get the latest build, and it needs adding repos … the steps will be doubled and may not work.
So I used fedora, the podman and CRI-O will be easy to install with the most resent released edition.

3. Select `[11] fedora` then install edition 36 `[1] 36`

Install minikube, podman and CRI-O

4. Install podman:

sudo dnf -y install podman

As of today this will install podman version 4.1.1 which is the newest edition like you build it from source…

5. Install CRI-O:

as you can see below it is easy to install CRI-O by setting the version to be installed after : as of today the latest version is 1.24

sudo dnf module enable cri-o:1.24
sudo dnf install cri-o

5. Install `containernetworking-plugins package`

Note: as of 1.24.0, the cri-o package no longer depends on containernetworking-plugins package. Removing this dependency allows users to install their own CNI plugins without having to remove files first. If users want to use the previously provided CNI plugins, they should also run:

sudo dnf install containernetworking-plugins

6. Install minikube

first install downloading tool wget:

sudo dnf install wget

Then Download Minikube binary:

sudo wget https://storage.googleapis.com/minikube/releases/latest/minikube-linux-amd64 -O /usr/local/bin/minikube

Finally, make it executable:

sudo chmod 0755 /usr/local/bin/minikube

6. Install kubectl (optional)

minikube has it its own kubectl, but you may like using the stand alone one

I recommend installing with native package management

First add the repo

cat <<EOF | sudo tee /etc/yum.repos.d/kubernetes.repo
[kubernetes]
name=Kubernetes
baseurl=https://packages.cloud.google.com/yum/repos/kubernetes-el7-x86_64
enabled=1
gpgcheck=1
repo_gpgcheck=1
gpgkey=https://packages.cloud.google.com/yum/doc/yum-key.gpg https://packages.cloud.google.com/yum/doc/rpm-package-key.gpg
EOF

Then install kubectl :

sudo dnf install kubectl -y

7. Start CRI-O service

This may not work in official Microsoft WSL distro (because of systemctl support)
first, it is recommended to reboot

sudo reboot

close the terminal and open again and enable the systemctl

sudo systemctl daemon-reload
sudo systemctl enable crio --now

check with this command sudo systemctl status crio
should give no error, something like :

crio.service - Container Runtime Interface for OCI (CRI-O)
     Loaded: loaded (/usr/lib/systemd/system/crio.service; enabl
ed; vendor preset: disabled)
     Active: active (running) since Sun 2022-07-03 22:26:54 +03; 4min 46s ago
       Docs: https://github.com/cri-o/cri-o
   Main PID: 208 (crio)
      Tasks: 11
     Memory: 30.6M
     CGroup: /system.slice/crio.service
             └─ 208 /usr/bin/crio

8. Adding Podman to sudoers

install nano:

sudo dnf install nano -y

then edit the sudoers file:

sudo nano /etc/sudoers

Append the following to the section at the very bottom of the file where username is your user account.

myuser ALL=(ALL) NOPASSWD: /usr/bin/podman

Be sure this text is after #includedir /etc/sudoers.d. To confirm it worked, try:

sudo -k -n podman version

8. Starting minikube:

it is better to download the image before starting the cluster.

minikube start --driver=podman --container-runtime=cri-o --download-only=true

Then

minikube start --driver=podman --container-runtime=cri-o

If it fails from the first time delete and try again without container runtime option then delete and try…

minikube delete

minikube start --driver=podman

minikube delete

minikube start --driver=podman --container-runtime=cri-o

That's it, Kubernetes will be working now