C++ vs. Python vs. PHP vs. Java vs. Others performance benchmark (2016 Q3)

/contrib/famzah

The benchmarks here do not try to be complete, as they are showing the performance of the languages in one aspect, and mainly: loops, dynamic arrays with numbers, basic math operations.

This is an improved redo of the tests done in previous years. You are strongly encouraged to read the additional information about the tests in the article.

Here are the benchmark results:

Language CPU time Slower than Language
version
Source
code
User System Total C++ previous
C++ (optimized with -O2) 0.899 0.053 0.951 g++ 6.1.1 link
Rust 0.898 0.129 1.026 7% 7% 1.12.0 link
1.090 0.006 1.096 15% 6% 1.8.0_102 link
1.376 0.120 1.496 57% 36% PyPy 5.4.1 link
C# .NET Core Linux 1.583 0.112 1.695 78% 13% 1.0.0-preview2 link
Javascript (nodejs) 1.371 0.466 1.837 93% 8% 4.3.1 link
Go 2.622 0.083 2.705 184% 47% 1.7.1 link
2.921 0.054 2.975

View original post 429 more words

C++ vs. Python vs. Perl vs. PHP performance benchmark (2016)

/contrib/famzah

There are newer benchmarks: C++ vs. Python vs. PHP vs. Java vs. Others performance benchmark (2016 Q3)

The benchmarks here do not try to be complete, as they are showing the performance of the languages in one aspect, and mainly: loops, dynamic arrays with numbers, basic math operations.

This is a redo of the tests done in previous years. You are strongly encouraged to read the additional information about the tests in the article.

Here are the benchmark results:

Language CPU time Slower than Language
version
Source
code
User System Total C++ previous
C++ (optimized with -O2) 0.952 0.172 1.124 g++ 5.3.1 link
1.332 0.096 1.428 27% 27% 1.8.0_72 link
1.560 0.160 1.720 53% 20% PyPy 4.0.1 link
Javascript (nodejs) 1.524 0.516 2.040 81% 19% 4.2.6 link
2.988 0.168 3.156 181% 55% g++ 5.3.1 link
PHP 7.0 6.524 0.184

View original post 222 more words

A multiplication algorithm found in a book by Paul Erdős: how does it work?

From stackoverflow

# -*- coding: utf-8 -*-
"""
Created on Mon Mar 20 09:08:06 2017

@author:
From Erdős and Surányi's Topics in the theory of numbers (Springer),
chapter 1 ("Divisibility, the Fundamental Theorem of Number Theory"):

We can multiply two (positive integer) numbers together
in the following way:
1. Write the two numbers down next to each other.
2. Divide the first in half, rounding down to an integer,
and write the result below it.
3. Double the second number, writing the result below it.
4. Continue this halving / doubling until we are left
with 1 in the first column.
5. Cross out all those numbers in the second column
that are opposite an even number and add the remaining
numbers in this column together to get the product.

Prove that this works.

This method is often called "Russian peasant multiplication".

It's often justified by thinking about writing the first number in binary.
Here's another way to explain it:
    At each step, we're replacing a pair (p,q) either by (p2, 2q)
    (when p is even) or by (p−1/2, 2q) (when p is odd).

    In the first case, when p is even, the product of the two numbers
    doesn't change: p⋅q=p/2 2p⋅.

    In the second case, when p is odd, p−1/2⋅2q=p⋅q−q.
    So the product has decreased by q, and we should set q aside for later.

    Eventually, we get to a pair (1,r) whose product is easy to compute:
        it's just r.
    Because we've kept track of how the product of a pair has changed,
    we know that the original product is equal to this product,
    plus all the numbers we've set aside. But we set aside q from the pair
    (p,q) whenever p is odd. So adding the numbers we set aside to the
    final number just corresponds to adding up the second number in every
    pair whose first number is odd.

The ancient Egyptains had a similar precursor method:
    en.wikipedia.org/wiki/Ancient_Egyptian_multiplication
    – Henno Brandsma Mar 17 at 4:55

Note this method can be adapted for other number bases,
there is nothing special about 2, except for the fact that it is
immediate to calculate mod 2 of a base 10 representation.
To adapt it for base b, divide by b in each step and record the
remainder, later multiply each reminder by the right column and add.
Also, stop the first column when reaching a number less than b.
The right column is generated by multiplying by b.

And this is an example, 73⋅217:
(73,217)(36,434)(18,868)(9,1736)(4,3472)(2,6944)(1,13888)
Then 73⋅217=217+1736+13888=15841, which is correct.
"""

def russian_peasant_multiplication(p, q, acc=0):
    '''
    Returns de product of a and b if acc == 0
    using recursive conversion of the first factor to binary
    '''
    print(p, q, acc + q)
    if p == 1:
        return acc + q
    elif (p % 2) == 0:
        return russian_peasant_multiplication(p // 2, q * 2, acc)
    else:
        return russian_peasant_multiplication(p // 2, q * 2, acc + q)

assert russian_peasant_multiplication(73, 217) == 15841

Artificial Intelligence – Depth First Search(DFS)

Algorithmic Thoughts - Artificial Intelligence | Machine Learning | Neuroscience | Computer Vision

Okay! So this is my first blog post!

I will start by talking about the most basic solution to search problems, which are an integral part of artificial intelligence.

What the hell are search problems?

In simple language, search problems consist of a graph, a starting node and a goal(also a node). Our aim while solving a search problem is to get a path from the starting node to the goal.

Consider the diagram below, we want to get to the node G starting from the node S.

Which path will we get on solving the search problem? How do we get the path? This is where algorithms come into picture and answer all our questions! We will look at Depth First Search which can be seen as a brute force method of solving a search problem.

Creating the search tree

So how do we simplify this problem? If we…

View original post 623 more words

Artificial Intelligence – A* Search Algorithm

Algorithmic Thoughts - Artificial Intelligence | Machine Learning | Neuroscience | Computer Vision

We will try to improve the efficiency of the Uniform Cost Search algorithm by using heuristics which we discussed in the previous post. By improving the efficiency I mean that the algorithm will expand less of the search tree and will give the optimal result faster. We start with the same search problem and search tree that we used for Uniform Cost Search. If you don’t know what search problems are or how search trees are created, visit this post.

searchProblem
searchTree
A* Search Algorithm

We saw that Uniform Cost Search was optimal in terms of cost for a weighted graph. Now our aim will be to improve the efficiency of the algorithm with the help of heuristics. If you don’t know what heuristics are, visit this post. Particularly, we will be using admissible heuristics for A* Search.

A* Search also makes use of a priority queue just like Uniform…

View original post 474 more words