Gues:t post in jupiter notebook:

Finding Fibonacci Numbers Using Lambda Calculus

Enjoy!

# Thoughts In Free Time

## Monday, 29 July 2019

## Thursday, 18 July 2019

### AVL Tree in Java

I have not blogged for some time, but there is something new: AVL Tree in Java. Code on github: https://github.com/lion137/Java .

Thanks, enjoy!

Thanks, enjoy!

## Monday, 4 March 2019

### Fundamental Algorithms: Parse to RPN

Another one, Parsing to Reverse Polish Notation. Why it's so important? For example, typing to the first calculators, one had to do it in RPN! It's very easy to find a value of an expression in RPN. Deadly simple, having one, like:

1 When we see a number push it on stack.

2. Seeing operand, pop stack twice, perform the operation and push result.

3. When done pop stack - this is result!

Parsing is not such easy, but is explained in details, for example, here.

Code on github.

Whole Series.

Thank you!

3 2 + 4 3 * +It's enough to take en empty LIFO stack, go through it and:

1 When we see a number push it on stack.

2. Seeing operand, pop stack twice, perform the operation and push result.

3. When done pop stack - this is result!

Parsing is not such easy, but is explained in details, for example, here.

Code on github.

Whole Series.

Thank you!

## Wednesday, 27 February 2019

### Fundamental Algorithms III

Three more fundamental algorithms in the series. Today, recursive permutations, subsets of the given set and variations with repetitions. The all written in C++ (non generic, I used std::vector). Code (hope it's self explanatory, any questions ask).

Whole series.

Thank you.

Whole series.

## Friday, 22 February 2019

## Sunday, 3 February 2019

### Fundamental Algorithms: Polynomial GCD

Another one in the series on fundamental algorithms; today: polynomial division. We assume, that polynomial is over some field, this is good thing, we have lots of nice properties in those; explicitly, if

So, division is easy, just "push it" over the field, like division in base, or multi precision division.

Algorithm, Knuth "The Art Computer Programming Vol 4" and the others:

Having division, we can compute the Great Common Divisor, showing, that Euclidean Domain is larger than expected:

The code, as usually on github , (division.py). Thank you, see you next time!

*a*and*b*are in the field and*b*is not zero, than there always exists an element of the field,*c*, such that*a = bc.*So, division is easy, just "push it" over the field, like division in base, or multi precision division.

Algorithm, Knuth "The Art Computer Programming Vol 4" and the others:

# input: coefficients of polynomials as a lists u, v != 0 # in order u[0] = free coefficient of u(x), .... # returns polynomials q, r such that u = vq + r(rest) # length u >= length v >= 0 def poly_divide(u, v): m = len(u) - 1 n = len(v) - 1 q = [0] * (m - n + 1) lim = m - n for k in range(lim, -1, -1): q[k] = u[n + k] / v[n] for j in range(n + k - 1, k - 1, -1): u[j] = u[j] - q[k] * v[j - k] return q, u[:n]

Having division, we can compute the Great Common Divisor, showing, that Euclidean Domain is larger than expected:

def poly_gcd(u, v): if not any(v): return u else: return poly_gcd(v, poly_mod(u, v))

*poly_mod*it's just a rest returned from division algorithm. I think it's beautiful, don't you?The code, as usually on github , (division.py). Thank you, see you next time!

Subscribe to:
Posts (Atom)