Piscataway, NJ – Tangent Works used Julia to win the IEEE Global Energy Forecasting Competition 2017 (GEFCom2017).

Tangent Works is a European machine learning company that conducts real time energy forecasting.

Out of 177 competition teams, Tangent Works was one of just two competitors to win both the qualifying match and the final match.

According to Jan Dolinsky, Chief Technology Officer at Tangent Works, “We relied 100% on Julia to win this competition. At the core of our product we do numerous matrix operations where we rely heavily on unique aspects of the language such as out of the box support of SIMD instruction sets, direct access to BLAS, broadcasting, syntactic loop fusion and others.”

Dr. Tao Hong, Chair of the IEEE Working Group on Energy Forecasting and General Chair of the Global Energy Forecasting Competition explains:

• “More than 300 students and professional from more than 30 countries formed 177 teams” to compete.
• “GEFCom2017 is the longest and most challenging among the series of Global Energy Forecasting Competitions. To encourage the contestants to explore opportunities in the big data world, GEFCom2017 released more data than the previous competitions combined.”
• “The theme is hierarchical probabilistic load forecasting. The 6-month-long GEFCom2017 includes two phases. The qualifying match was to provide medium term probabilistic forecasts for the ISO New England region in real time. The final match asked the contestants to provide probabilistic forecasts for 161 delivery points.”

Julia is the fastest high performance open source computing language for data, analytics, algorithmic trading, machine learning, artificial intelligence, and many other domains. Julia solves the two language problem by combining the ease of use of Python and R with the speed of C++. Julia provides parallel computing capabilities out of the box and unlimited scalability with minimal effort. For example, Julia has run at petascale on 650,000 cores with 1.3 million threads to analyze over 56 terabytes of data using Cori, the world’s sixth-largest supercomputer. With more than 1.2 million downloads and +161% annual growth, Julia is one of the top programming languages developed on GitHub. Julia adoption is growing rapidly in finance, insurance, machine learning, energy, robotics, genomics, aerospace, medicine and many other fields.

Julia Computing was founded in 2015 by all the creators of Julia to develop products and provide professional services to businesses and researchers using Julia. Julia Computing offers the following products:

• JuliaPro for data science professionals and researchers to install and run Julia with more than one hundred carefully curated popular Julia packages on a laptop or desktop computer.
• JuliaRun for deploying Julia at scale on dozens, hundreds or thousands of nodes in the public or private cloud, including AWS and Microsoft Azure.
• JuliaFin for financial modeling, algorithmic trading and risk analysis including Bloomberg and Excel integration, Miletus for designing and executing trading strategies and advanced time-series analytics.
• JuliaDB for in-database in-memory analytics and advanced time-series analysis.
• JuliaBox for students or new Julia users to experience Julia in a Jupyter notebook right from a Web browser with no download or installation required.

To learn more about how Julia users deploy these products to solve problems using Julia, please visit the Case Studies section on the Julia Computing Website.

Julia users, partners and employers hiring Julia programmers in 2017 include Amazon, Apple, BlackRock, Capital One, Citibank, Comcast, Disney, Facebook, Ford, Google, IBM, Intel, KPMG, Microsoft, NASA, Oracle, PwC, Uber, and many more.

Tangent Works is a European machine learning company providing the next generation of prediction solutions for businesses by automating the predictive model building process. With its breakthrough solution, TIM, companies can now generate accurate predictive models for time series analysis in seconds, fully automatic, as a transparent formula providing useful insights about the dynamics hidden in the data. TIM eliminates the data science skills burden, and is extremely efficient on computing time which allows machine learning solutions to be executed directly on a device. The core of the technology is applicable for a variety of advanced analytics challenges such as time series analysis, complex pattern recognition, anomaly detection and classification. Tangent Works was initiated in 2013 by four experienced partners, combining advanced machine learning knowledge, software product development, and years of international marketing & sales development in high tech environments. The company employs 15 specialists in offices in Belgium and Slovakia.

By: Mosè Giordano

Re-posted from: https://giordano.github.io/blog/2017-11-21-hexadecimal-pi/

The
Bailey–Borwein–Plouffe formula is
one of the
several
algorithms to compute $\pi$.
Here it is:

$$\pi = \sum_{k = 0}^{\infty}\left[ \frac{1}{16^k} \left( \frac{4}{8k + 1} - \frac{2}{8k + 4} - \frac{1}{8k + 5} - \frac{1}{8k + 6} \right) \right]$$

What makes this formula stand out among other approximations of $\pi$ is that
it allows one to directly extract the $n$-th fractional digit of the
hexadecimal value of $\pi$ without computing the preceding ones.

Image credit: Cormullion, Julia
code
here.

The Wikipedia article about the Bailey–Borwein–Plouffe formula explains that the
$n$-th fractional digit (well, actually it’s the $n+1$-th) $d_{n}$ is
given by

$$d_{n} = 16 \left[ 4 \Sigma(n, 1) - 2 \Sigma(n, 4) - \Sigma(n, 5) - \Sigma(n, 6) \right]$$

where

$$\Sigma(n, j) = \sum_{k = 0}^{n} \frac{16^{n-k} \bmod (8k+j)}{8k+j} + \sum_{k = n+1}^{\infty} \frac{16^{n-k}}{8k+j}$$

Only the fractional part of expression in square brackets on the right side of
$d_{n}$ is relevant, thus, in order to avoid rounding errors, when we compute
each term of the finite sum above we can take only the fractional part. This
allows us to always use ordinary double precision floating-point arithmetic,
without resorting to arbitrary-precision numbers. In addition note that the
terms of the infinite sum get quickly very small, so we can stop the summation
when they become negligible.

Implementation in Julia language

Here is a Julia implementation of the algorithm to
extract the $n$-th fractional digit of $\pi$:

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



# Return the fractional part of x, modulo 1, always positive
fpart(x) = mod(x, one(x))

function Σ(n, j)
    # Compute the finite sum
    s = 0.0
    denom = j
    for k in 0:n
        s = fpart(s + powermod(16, n - k, denom) / denom)
        denom += 8
    end
    # Compute the infinite sum
    num = 1 / 16
    frac = num / denom
    while frac > eps(s)
        s     += frac
        num   /= 16
        denom += 8
        frac   = num / denom
    end
    return fpart(s)
end

pi_digit(n) =
    floor(Int, 16 * fpart(4Σ(n-1, 1) - 2Σ(n-1, 4) - Σ(n-1, 5) - Σ(n-1, 6)))

pi_string(n) = "0x3." * join(hex.(pi_digit.(1:n))) * "p0"

The pi_digit function gives the $n$-th hexadecimal fractional digit of
$\pi$ as a base-10 integer, and the pi_string function returns the first
$n$ hexadecimal digits of $\pi$ as a valid hexadecimal floating-point
literal:

julia> pi_digit(1)
2

julia> pi_digit(6)
10

julia> pi_string(1000)
"0x3.243f6a8885a308d313198a2e03707344a4093822299f31d0082efa98ec4e6c89452821e638d01377be5466cf34e90c6cc0ac29b7c97c50dd3f84d5b5b54709179216d5d98979fb1bd1310ba698dfb5ac2ffd72dbd01adfb7b8e1afed6a267e96ba7c9045f12c7f9924a19947b3916cf70801f2e2858efc16636920d871574e69a458fea3f4933d7e0d95748f728eb658718bcd5882154aee7b54a41dc25a59b59c30d5392af26013c5d1b023286085f0ca417918b8db38ef8e79dcb0603a180e6c9e0e8bb01e8a3ed71577c1bd314b2778af2fda55605c60e65525f3aa55ab945748986263e8144055ca396a2aab10b6b4cc5c341141e8cea15486af7c72e993b3ee1411636fbc2a2ba9c55d741831f6ce5c3e169b87931eafd6ba336c24cf5c7a325381289586773b8f48986b4bb9afc4bfe81b6628219361d809ccfb21a991487cac605dec8032ef845d5de98575b1dc262302eb651b8823893e81d396acc50f6d6ff383f442392e0b4482a484200469c8f04a9e1f9b5e21c66842f6e96c9a670c9c61abd388f06a51a0d2d8542f68960fa728ab5133a36eef0b6c137a3be4ba3bf0507efb2a98a1f1651d39af017666ca593e82430e888cee8619456f9fb47d84a5c33b8b5ebee06f75d885c12073401a449f56c16aa64ed3aa62363f77061bfedf72429b023d37d0d724d00a1248db0fead3p0"

While I was preparing this post I found an unregistered
package PiBBP.jl that implements the
Bailey–Borwein–Plouffe formula. This is faster than my code above, mostly
thanks to a function
for
modular exponentiation
more efficient than that available in Julia standard library.

Test results

Let’s check if the function is working correctly. We can use
the
parse function
to convert the string to a decimal floating point
number. IEEE 754 double precision
floating-point numbers have a 53-bit mantissa, amounting to $53 / \log_{2}(16) \approx 13$ hexadecimal digits:

julia> pi_string(13)
"0x3.243f6a8885a30p0"

julia> parse(Float64, pi_string(13))
3.141592653589793

julia> Float64(π) == parse(Float64, pi_string(13))
true

Generator expressions allow
us to obtain the decimal value of the number in a very simple way, without using
the hexadecimal string:

julia> 3 + sum(pi_digit(n)/16^n for n in 1:13)
3.141592653589793

We can use
the
arbitrary-precision BigFloat
to check the correctness of the result for even more digits. By default,
BigFloat numbers in Julia have a 256-bit mantissa:

julia> precision(BigFloat)
256

The result is correct for the first $256 / \log_{2}(16) = 64$ hexadecimal
digits:

julia> pi_string(64)
"0x3.243f6a8885a308d313198a2e03707344a4093822299f31d0082efa98ec4e6c89p0"

julia> BigFloat(π) == parse(BigFloat, pi_string(64))
true

julia> 3 + sum(pi_digit(n)/big(16)^n for n in 1:64)
3.141592653589793238462643383279502884197169399375105820974944592307816406286198

It’s possible to increase the precision of BigFloat numbers, to further test
the accuracy of the Bailey–Borwein–Plouffe formula:

julia> setprecision(BigFloat, 4000) do
           BigFloat(π) == parse(BigFloat, pi_string(1000))
       end
true

Multi-threading

Since the Bailey–Borwein–Plouffe formula extracts the $n$-th digit of $\pi$
without computing the other ones, we can write a multi-threaded version of
pi_string, taking advantage of native support
for
multi-threading
in Julia:

1
2
3
4
5
6
7



function pi_string_threaded(N)
    digits = Vector{Int}(N)
    Threads.@threads for n in eachindex(digits)
        digits[n] = pi_digit(n)
    end
    return "0x3." * join(hex.(digits)) * "p0"
end

For example, running Julia with 4 threads gives a 2× speed-up:

julia> Threads.nthreads()
4

julia> using BenchmarkTools

julia> pi_string(1000) == pi_string_threaded(1000)
true

julia> @benchmark pi_string(1000)
BenchmarkTools.Trial:
  memory estimate:  105.28 KiB
  allocs estimate:  2016
  --------------
  minimum time:     556.228 ms (0.00% GC)
  median time:      559.198 ms (0.00% GC)
  mean time:        559.579 ms (0.00% GC)
  maximum time:     564.502 ms (0.00% GC)
  --------------
  samples:          9
  evals/sample:     1

julia> @benchmark pi_string_threaded(1000)
BenchmarkTools.Trial:
  memory estimate:  113.25 KiB
  allocs estimate:  2018
  --------------
  minimum time:     270.577 ms (0.00% GC)
  median time:      271.075 ms (0.00% GC)
  mean time:        271.598 ms (0.00% GC)
  maximum time:     278.350 ms (0.00% GC)
  --------------
  samples:          19
  evals/sample:     1

Julia has 3 kinds of parallelism.
The well known, safe, slowish and easyish, distributed parallelism, via pmap, @spawn and @remotecall.
The wellish known, very safe, very easy, not-actually-parallelism, asynchronous parallelism via @async.
And the more obscure, less documented, experimental, really unsafe, shared memory parallelism via @threads.
It is the last we are going to talk about today.

I’m not sure if I can actually teach someone how to write threaded code.
Let alone efficient threaded code.
But this is me giving it a shot.
The example here is going to be fairly complex.
For a much simpler example of use,
on a problem that is more easily parallelizable,
see my recent stackoverflow post on parallelizing sorting.

(Spoilers: in the end I don’t manage to extract any serious performance gains from paralyzing this prime search. Unlike parallelizing that sorting. Paralising sorting worked out great)

Continue reading →