CodePlea

Random thoughts on programming
23 Aug 2016

Exponentiation Associativity and Standard Math Notation


Someone recently told me that TinyExpr (my math expression evaluation library) had several bugs, mostly related to the precedence and associativity of the exponentiation operator. It turned out that they thought that math notation was more standardized than it actually is.

I made TinyExpr to be used in a spreadsheet-like program. Therefore, I tried to make it somewhat compatible with spreadsheets. This makes for behavior that may surprise some people. For example, TinyExpr evaluates multiple exponentiation from left-to-right by default. This behaviour is clearly documented in the Readme and can be changed with a compile-time flag.

I thought it'd be nice to do a survey of common computer languages and tools and see how they handle exponentiation precedence and associativity.


Left or Right Associativity of the Exponentiation Operator?

Left exponentiation associativity works like this: 2^2^3 == (2^2)^3 == 64.

Right exponentiation associativity works like this: 2^2^3 == 2^(2^3) == 256.

Many people would say that right associativity is more useful since (a^b)^c == a^(b*c) anyway. However, which is correct? I'd say neither is correct, because there is no widely agreed upon standard.

Let's see how other people handle it:

What Code Tested Result Associativity
Bash 2**2**3 256 right-associative
C++ a^b^c 64 left-associative
DuckDuckGo 2^2^3 256 right-associative
Excel 2^2^3 64 left-associative
EtherCalc 2^2^3 64 left-associative
Fortran 2**2**3 256 right-associative
Google 2^2^3 256 right-associative
Google Sheets 2^2^3 256 right-associative
Hand-held Calculators Varies
Lua 2^2^3 256 right-associative
Matlab 2^2^3 64 left-associative
Octave 2^2^3 64 left-associative
Perl 2**2**3 256 right-associative
PostgreSQL 2^2^3 64 left-associative
Python 2**2**3 256 right-associative
Ruby 2**2**3 256 right-associative
Tcl 2**2**3 256 right-associative
WolframAlpha 2^2^3 256 right-associative

Notes

  • Am I being disingenuous in the C++ example? I don't think so. C++ programmers write this stuff.
  • There is an interesting writeup on TCL here.

Variable Negation or Exponentiation First?

Another apparent issue is what to do first in an expression such as -2^2. Should it be (-2)^2 == 4 or -(2^2) == -4? Let's find out!

What Code Tested Result First Step
Bash -2**2 4 negation
DuckDuckGo -2^2 4 negation
Excel -2^2 4 negation
EtherCalc -2^2 4 negation
Fortran -2**2 -4 exponentiation
Google -2^2 -4 exponentiation
Google Sheets -2^2 4 negation
Handheld Calculators -2^2 Varies
Lua -2^2 -4 exponentiation
Matlab -2^2 -4 exponentiation
Octave -2^2 -4 exponentiation
Perl -2**2 -4 exponentiation
PostgreSQL -2^2 4 negation
Python -2**2 -4 exponentiation
Ruby -2**2 -4 exponentiation
Tcl -2**2 4 negation
WolframAlpha -2^2 -4 exponentiation

Conclusions

I don't think you can claim any one method is correct or incorrect. There simply is no widely agreed-upon standard.

For this reason I've made TinyExpr default to Excel-like behaviour, but it can be changed with a compile-time flag.

Also, you should really just use parentheses. If you don't, you're going to have a bad day sooner or later.

18 Mar 2016

Genann - Neural Network Library


I've made a simple neural network library in ANSI C called Genann. I released it as open-source on github recently. You can find it here.

A primary design goal of Genann was to be both complete and minimal. I'm happy with how close I've come to that goal. Genann implements the feed-forward algorithm, backpropagation, and not much else. It's not opinionated about how you store your data or about how you do training. It is contained in just a single C source file and header file.

Genann is also very easy to use. For example, creating a network with 2 inputs, 3 hidden neurons, and 2 outputs is as easy as:

/* inputs, hidden layers, neurons per hidden layer, outputs. */
genann *ann = genann_init(2, 1, 3, 2);

Example neural network connection structure.

That also creates the needed bias node connections automatically.

Training with backpropagation is simply:

/* genann, input array, output array, learning rate. */
genann_train(ann, inputs, expected_outputs, 0.1);

Doing a feed-forward pass is only:

double const *prediction = genann_run(ann, inputs);

Genann implements backpropagation, of course, but it also has another trick that most ANN libraries ignore. Backpropagation is good for supervised learning, but not reinforcement learning. Genann supports reinforcement learning by keeps all of its weights in one contiguous block of memory. This means that it is very easy to optimize the weights directly using numerical optimization techniques, such as the genetic algorithm.

If you have need for a minimal, no-frills ANN library in ANSI C, I encourage you to take a look at Genann. You can find documentation and several examples here.

23 Feb 2016

Apple and the FBI


The FBI has gotten a court order demanding that Apple help unlock a San Bernardino shooter's work phone, an iPhone 5C.

This has been in the news everywhere for days, and I'm already sick of it, so I'm going to keep this short.

Almost everyone has read Apple's public response, but nobody I've talked to has read the actual court order itself. You're doing yourself a disservice if you don't read the actual court order for yourself. It's three pages, and it's much more precise than Apple's response or anything you'll read in the news.

From the order, we see that the government is asking Apple to do three things:

  1. Disable the auto-erase function
  2. Allow a way to submit passwords automatically (without fingers on touchscreen)
  3. Prevent the device from taking longer than necessary to check passwords

Here's the thing: Apple is taking the stance that they don't want to weaken their product's security. That's great. However, I think Apple is actually weakening their security by not complying, or at the very least they're publicly admitting that their security is already weak.

The court has asked Apple to do nothing that a well-funded adversary couldn't already do on their own.

Strong encryption should stand up to an adversary that already knows everything (except the encryption key itself). If your security relies on the adversary not knowing some detail then you are relying on security through obfuscation. It's 2016, we can do better.

So while I applaud Apple's stance for not wanting to weaken their security, I say if their compliance with the court order significantly weakens their security, then their security was already poor to begin with.

11 Feb 2016

Succinct Code


I like simple things. It should be self-evident - I recently ditched WordPress for a hundred lines of PHP and flat-files. I'm much happier for it.

I used to write a lot of C++ code, but for the last several years I've completely eschewed it in favor of C. I can't ever see myself ever going back to C++, as I feel like C is a better language, and it's much easier to keep a large project nice and neat using it. C++ code has a tendency to grew crufty almost from the start. C++ has more abstractions, and although all abstracts are leaky, I think C++ lends itself to creating especially leaky abstractions. C++ makes it much easier to build yourself into a corner compared to C.

Anyway, a few days ago I witnessed an exchange on Stack Overflow that I thought was interesting. It pretty well illustrated some of the differences I find between C and C++ code. And also showcased some of the problems I have with Stack Overflow in general.

While keeping an eye on the new tab, a question about random number generators in C++ came up. A kind answerer posted the following code as an example of a linear congruential generator.

unsigned int seed = 12345;

unsigned int random() {
    seed = (1664525 * seed + 1013904223);
    return seed;
}

In my opinion, this is excellent code for it's purpose. It's succinct, and it demonstrates exactly the LCG algorithm and nothing more. It's excellent teaching code.

Of course, it seems that my opinion is the minorities'. Almost immediately I watched this answer get down-votes and negative comments. Comments like "Global variables are evil!" "This belongs in a class!" etc.

The question wasn't about global variables. Anyone with a modicum of proficiency in C knows ten different ways to refactor out the global seed variable. And the code has much larger impediments to real world usage than its global variable (such as the inherent limitations of the LCG algorithm). But the code is great for illustration of the algorithm, and I thought that's what Stack Overflow was about.

Another user noticed the trend and decided to capitalize on the opportunity to gain rep. Not long after the original answer, he posted the following code:

class Random
{
    private:
        unsigned int seed;

    public:
        Random(unsigned int s);
        unsigned int next();
};

Random::Random(unsigned int s)
{
    seed = s;
}

unsigned int Random::next()
{
    seed = (1664525 * seed + 1013904223);
    return seed;
}

This longer, more verbose, needlessly abstracted, C++ code quickly gained up-votes, positive comments, and was later accepted as the official answer. It reminded me of why I don't generally like C++. It's all the boilerplate. Making a class is like filling out tax forms. It's tedious and boring. It provides friction to creating anything and especially to refactoring anything. And for what advantage?

Eventually the moderators closed the question as a duplicate, the first answerer deleted his answer, and everybody lost. The end.

01 Feb 2016

Ditching Wordpress


This site has been running WordPress since the beginning.

Today I moved it to my own CMS (which I will open-source one of these days). I've integrated comments using Disqus.

WordPress isn't bad per se, but it tries to do everything. That makes it extremely complex. I like simple things. Now I feel like I can really tweak the site's functionality. I think I'll be much happier going forward with my flat-file CMS.

Hopefully nothing was broken in the transfer. I think all the URLs have stayed the same and all the old comments transferred over.