Wednesday, 17 May 2017

Thursday, 30 March 2017

New Class in C++ Biginteger Library!

I've started developing a C++ wrapper for GMP - high precision arithemtic library in C; updates on github today - bigrationals added! Only basic functions for now, but development in progress:)

Thursday, 23 March 2017

C++ GMP Wrapper

Recently beeing busy - writing, in C++, wrapper for GMP LibraryCode here - you are invited to improve it!:)

Wednesday, 8 March 2017

Scala Trees

Recently, I've been playing with functional programming, ADT to be precise, and this is the outcome - trees implementation in Scala.
Data are created in common way as a Scala trait:

sealed trait Tree[+A]
case object EmptyTree extends Tree[Nothing]
case class Node[A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A]

All looks Okay, lets create some trees and functions.

val tree = Node(10, Node(5, EmptyTree, EmptyTree), Node(15, EmptyTree, EmptyTree))

No problem, but at least for integer binary trees, we can right now do better: create a function to join elements to the tree:

def addToTree(elem: Int, tree: Tree[Int]): Tree[Int] = {
if (isTreeEmpty(tree)) Node(elem, EmptyTree, EmptyTree)
else if (elem == loadTree(tree)) tree
else if (elem < loadTree(tree)) Node(loadTree(tree), addToTree(elem, leftBranch(tree)), rightBranch(tree))
else Node(loadTree(tree), leftBranch(tree), addToTree(elem, rightBranch(tree)))
  }

This is the standard way to add elements to a binary tree, we can use it in a loop and don't need to worry about memory - we use persistent data structure.

Two sample functions operate on a tree:

def length[A](tree: Tree2[A]): Int =
tree match {
case EmptyTree => 0
case Node(x, left, right) => length2(left) + 1 + length2(right)
  } 

def maxDepth[A](tree: Tree2[A]): Int =
tree match {
   case EmptyTree => 0
   case Node(x, left, right) =>
   var lmax = maxDepth2(left)
   var rmax = maxDepth2(right)
   if (lmax > rmax) lmax + 1
      else rmax + 1
    }

They do what their names promise: count nodes and maximum depth of the trees. Finally map over the tree:

def treeMap[A, B](tree: Tree2[A])(f: A => B): Tree2[B] =
tree match {
case EmptyTree => EmptyTree
case Node(x, left, right) => 
Node(f(x), tree2Map(left)(f), tree2Map(right)(f))
  }
We can, in a similar way, all the needed function like foldl, traversing a tree and more. Code, including not implemented here functions helped to design joining element to tree, as usually on github. Till the next time!

Monday, 20 February 2017

Graphs in Python

In one of the post from series Python Data Structures I promised, that graphs come to the family, so here they are.
Design, I decided to adjacency list implementation, as underlying data structures there are: a list of vertices and list of lists (list of adjacent vertices for any given). I could have used a symbol table (more operation), but decided to keep things as simple as possible (graph algorithms are complicted on its own). A sample of code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
# Simple graph API in Python, implementation uses adjacent lists.
# look also here:
# Classes: Graph, Depth_first_search, Depth_first_paths
# Usage:
# Creating new graph: gr1 = Graph(v) - creates new
# graph with no edges and v vertices;

# Search object: gr2 = Depth_first_search(graph, vertex) -
# creates search object,
# gr2.marked_vertex(vertex) - returns true if
# given vertex is reachable from source(above)

# Path object: gr3 = Depth_first_paths(graph, vertex)-
# creates a new path object,
# gr3.has_path(vertex) - thee same as above
# gr3.path_to(vertex) - returns path from source vertex (to the given)
from collections import deque


class Graph:
    """Class graph, creates a graph - described by integers - number
    of vertices - V : v0, v1, ..., v(V-1)"""

    def __init__(self, v_in):
        """constructor -  takes number of vertices and creates a graph
         with no edges (E = 0) and an empty adjacent lists of vertices"""
        self.V = v_in
        self.E = 0
        self.adj = []
        for i in range(v_in):
            self.adj.append([])

    def V(self):
        """returns number of vertices"""
        return self.V

    def E(self):
        """returns number of edges"""
        return self.E

    def add_edge(self, v, w):
        """adds an edge to the graph, takes two integers (two vertices)
         and creates an edge v,w - by modifying appropriate adjacent lists """
        self.adj[v].append(w)
        self.adj[w].append(v)
        self.E += 1

    def adj_list(self, v):
        """Takes an integer - a graph vertex and returns the adjacency lists of it"""
        return self.adj[v]

    def __str__(self):
        """to string method, prints the graph"""
        s = str(self.V) + " vertices, " + str(self.E) + " edges\n"
        for v in range(self.V):
            s += str(v) + ": "
            for w in self.adj[v]:
                s += str(w) + " "
            s += "\n"
        return s


class Depth_first_search:
    """class depth forst search, creates an object,
    constructor takes graph and a vertex"""

    def __init__(self, gr_obj, v_obj):
        self.marked = [False] * gr_obj.V
        self.cnt = 0
        self.__dfs(gr_obj, v_obj)

    def __dfs(self, gr, v):
        """private depth first search, proceed recursively,
        mutates marked - marks the all possible to reach
         from given (v) vertices; also mutates cnt - number of visited vert"""
        self.marked[v] = True
        self.cnt += 1
        for w in gr.adj_list(v):
            if self.marked[w] == False:
                self.__dfs(gr, w)

    def marked_vertex(self, w):
        """Takes an integer - a graph vertex and returns True if it's reachable
        from vertex v (source)"""
        return self.marked[w]

    def count(self):
        """returns number of visited verticles
        (from given in the constructor vertex)"""
        return self.cnt

Why I did it in the java style? (Additional classes to given graph opertions) Primarly to avoid set and mutate global variables (in that case cnt in class Depth_first_search, I don't know how to solve it using function no object :/), also there is lots of graph tasks and operatons, and, imo, this approach is more clear (Did I really write this?:)). There are  going to be updates on this definitely! Code obviously, also on github. Thanks, till the next time!

Thursday, 9 February 2017

Bit Hacks in Go

Some time ago I wrote about little bit tweddlings in C, I, recently, have tried something similar in GO. It's not easy, for example bit shifts (>>) works only for unsigned integers and other differences. For now I reproduced and tested two things (both work on unsigned ints):  
Integer mean without casing an overflow and exponenation by binary decomposition.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func iexp(x uint32, n uint32) uint32 {
   if (n == 0) {
    return 1
   }
   var p, y uint32 
   y = 1;
   p = x;
   for {
    if (n & 1 != 0) {y = p*y}
     n >>= 1;
    if (n == 0) {return y}
     p *= p;
   }
  return 0
 }
Above is about 4 to 5 times faster than math.Pow from library.
Average:

1
2
3
func average(x uint32, y uint32) uint32 {
 return (x & y) + ((x ^ y) >> 1)
}

This time the adventage is not speed, but the fact, that we have the average without overflow (works,  for ex., for:, 2^32 - 1 and 2^32 - 1).  
That's it, code also on github, till the next time!

Tuesday, 7 February 2017

Python Pollard's rho Algorithm

I've recently was looking for some number theoretic algorithms in Python and Go. While searching, found this  on the first position on duckduckgo and google but it's not really good. Even for example used (1200), gives wrong answer (missing factor 600).  
Applying small fix:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def pollard_rho(n):
    s = set()
    i = 0
    xi = randint(0, n-1)
    y = xi
    k = 2
    while i < 2 * n:
        i += 1
        xi = ((xi^2) - 1)%n
        d = gcd(y - xi, n)
        if d != 1 and d != n:
            s.add(d)
        if i == k:
            y = xi
            k *= 2
    return sorted(s)

Where gcd is Greater Common Divisor, 2 * n in line 7, makes it work correctly, but it's still slow.
Anybody needs more efficient factorization (and more), I would recommend this library.