Nuclear Gandhi & Binary Arithmetic

Nuclear Gandhi is the nickname given to the Indian historical figure Mahatma Gandhi as portrayed in the turn-based strategy video game series Civilization.

A bug in the game caused Gandhi, who is a known pacifist in real life, to turn into a nuclear-obsessed maniac that made India the most hostile civilization in the game.

The cause was a glitch in the artificial intelligence settings for Gandhi’s aggression level: Gandhi started with the lowest level of aggression to reflect his historical legacy of pacifism: 1.

When a player adopted democracy in Civilization, their aggression would be automatically reduced by 2, which means that Gandhi’s aggression level should have gone to -1, but instead the aggression level went all the way up to 255, making him as aggressive as a civilization could possibly be.

Interesting right? but how the heck does -1 become 255?

A bit of math

Don’t worry. I’m not going to dive in too deep. There’s a plethora of blog posts and explanations on how integer arithmetic & representation work.

I’ll explain just enough in order for you to understand what’s going on.

Integer representation

510{5_{10}} in 8-bit binary is000001012{000001012}, pretty straight forward.
But what about510{-5{10}}? How is it implemented? lets draft a possible solution.

First, we need to know the sign of the number. We’ll reserve the most significant bit for the sign, and use the rest as the values. Second, We’ll make sure we don’t break compatibility and set the sign bit for positive numbers to zero, and negative numbers to one. In this scenario a
signed 8-bit number would range from -127 to 127.

Now, in our hacky system,510{5{10}} won’t change, and510{-5{10}} will be100001012{10000101_2}.

But here’s the catch - regular arithmetic doesn’t work:

510+510=000001012+100001012=100010102=10100{5{10}} + {-5{10}} = {00000101_2} + {10000101_2} = {100010102} = {-10{10}} \ne 0

We can build custom assembly arithmetic, but that’s an over-kill.

Two’s complement

Two’s complement is a mathematical operation on binary numbers, as well as a binary signed number representation based on this operation. Its wide use in computing makes it the most important example of a radix complement. - Wikipedia

TL;DR: a different system that makes arithmetic work as you’d expect.

// 00000101
int x = 5;
// ~x = 11111010
// ~x + 1 = 11111011
int negativeX = ~x + 1;

For example, addition of510{5{10}} and510{-5{10}} works like we expect:510+510=000001012+111110112=000000002{5{10}} + {-5{10}} = {00000101_2} + {11111011_2} = {00000000_2}

More information is out of scope for this blog post. If you’re interested, start from the answers for What is “2’s Complement”? on StackOverflow.

Ok, so what happened?

A Civilization’s aggression level was saved as an unsigned char, which can’t represent negative values.

Gandhi’s aggression level started at110{1{10}}, and when democracy arrived, it was reduced by two:110210=000000012000000102=000000012+111111102=111111112{1{10}} - {2_{10}} = {00000001_2} - {00000010_2} = {00000001_2} {\color{red} +} {11111110_2} = {11111111_2}

if the aggression level variable was signed, then the binary would be interpreted as110{-1{10}}, which is what we’d expect. Instead, it was unsigned, which means it got interpreted as25510{255{10}}.

… And Gandhi turned from a pacifist into a warmonger: “Greating from M. Gandhi, ruler and king of the Indians… Our words are backed with NUCLEAR WEAPONS!”

Do you REALLY understand floating points?

I’m going to ask you a couple of questions. If you answer all of them correctly, and understand why - good job! this post is not for you.

Otherwise, If you’re a normal human being, consider reading this post. It’ll save you hours of useless debugging. Honestly, If the engineering who built Ariane V read it (and set their compiler to warning as error) their rocket wouldn’t blow up.

What’s the answer? yes or no?

float x = 0.7;
printf(x == 0.7 ? "yes" : "no")

What will be printed?

float x = 4 / 3;
printf("%f", x);

What’s the answer? yes or no?

float x = 1.0/3.0;
double y = 1.0/1234567.0;
printf(((x+y) - x) == y ? "yes" : "no");

Are both lines equal?

float x = 0.20;
double y = 0.20;
printf("%4.20f\n", x);
printf("%4.20f\n", y);

Now that I’ve got your attention, lets go over the answers real quick. Once you get to the end of this blog post, You’ll understand them fully and be able to impress your coworkers with useless knowledge.

float x = 0.7;
printf(x == 0.7 ? "yes" : "no")

output: no.

float x = 4 / 3;
printf("%.3f", x);

output: 1.000

float x = 1.0/3.0;
double y = 1.0/1234567.0;
printf(((x+y) - x) == y ? "yes" : "no");

output: no.

float x = 0.20;
double y = 0.20;
printf("%4.20f\n", x);
printf("%4.20f\n", y);

output:

0.20000000298023223877
0.20000000000000001110

Read More

1st place @ HackIDC 2017

Yesterday, after 24 hours of hard work, zero sleep & a lot of fun, We won first place at HackIDC!

[The team by order of appearance: Carmel Rabinovitz, Nadav Eliyahu, Amir Livne, Inbal Ben Yehuda & Me]

What is HackIDC

HackIDC is Israel’s leading student Hackathon, held annually at IDC Herzliya. It is a great opportunity to build something new and exciting, together with coding and design enthusiasts. Students work in teams of up to five people for 24 hours to create a web, mobile, or hardware product.

What we did

Our team crafted a smart bracelet for conferences that swaps contact details between participants using a regular handshake. The match is done by monitoring acceleration data gathered from the bracelet’s Red Amber chip, and processing it in real-time by a learning algorithm that we developed.

The data that we collected could help conference organizers gain tremendous knowledge about the participants, and that’s only the beginning. We’re planning on continuing the project by adding more insightful features.

! All the sensor related tools were written in C++, MatLab helped us make sense of them. The data crunching part was written in python, and the website using WiX.

[The prototype we used during development]

Electra Challenge

HackIDC introduced a new “Challenge” section this year. Some of the sponsors had their own challenges for the teams: Bank Leumi, Murata & Electra.

We decided to participate in Electra’s challenge in parallel to our “main” solution - hook into an air conditioner unit to provide alerts to operation teams when interesting events occur:

  • A unit installation failed
  • Compressor gas had reached a critical point

We extracted all the sensor data straight from the unit, sent it to a server at the backend that crunched it, and raised alerts when they matched a pattern.

! The entire project was written in python. The frontend used flask, bootstrap and JS.

[The website showed real alerts raised by the data that was simulated by Electra’s air condition unit]

switch is much more than a glorified if

this post is a bit low level. I’ve been writing a lot of C & C++ recently, and found a few concepts eye opening. This post is dedicated to all the people that think that switch is a glorified if.

I’m going to do my best to avoid writing a lot of assembly, and make this post as easy as possible. Don’t worry if you don’t know any assembly, I’ll explain everything!

Read More

BASH Pitfalls & How to avoid them

Disclaimer: I’m using fish shell on my laptop. It solves everything that’s wrong with Bash, and is much more fun.

A few days ago I posted Test your terminal skills #1 to reddit. A few folks opened my eyes regarding the quality of my solutions, and directed me to two great resources.

Bash Pitfalls

Greg’s Bash Guide - A guide tht aims to aid people interested in learning to work with BASH. It aspires to teach good practice techniques for using BASH, and writing simple scripts.

Also, There’s a whole section for Bash Pitfalls, which is worth a read.

“Strict Mode”

Your bash scripts will be more robust, reliable and maintainable if you start them like this:

#!/usr/bin/env bash
set -euo pipefail
IFS=$'\n\t'

Why? Read Aaron Maxwell’s excellent blog post: Use the Unofficial Bash Strict Mode.

ShellCheck

ShellCheck finds bugs in your bash shell scripts.

You can grab it from here, or just paste your script to its website.
It integrates well with syntastic & neomake, which makes it extremely powerful.

If you know of any other resources for common pitfalls, please comment below!

Test your terminal skills #1

Today we’ll write a few scripts that parse the plain text version of the book Alice in Wonderland, and generate simple statistics.

Tasks

  1. Splits each chapter in the book into a dedicated file under the ‘chapters’ directory. There should be 12 chapters when you’re done.

  2. Generates statistics for the whole book, and each chapter:

    • The most frequently used word
    • The least frequently used word
    • The longest word
  3. Find the amount of words that their length is bigger than the average word length in the entire book.

  4. Find the “closest” word to “Alice” - the most frequently used word that appeared right before or after the word “Alice”.

Read more if you want to see my solutions.

Read More

Language Server Protocol

The Language Server Protocol (LSP) is an open protocol created & lead by Microsoft that defines a common language for programming language analyzers to speak. I’m extremely excited about it, and I believe that once your read more about it, you would too.

From the official LSP specification:

The Language Server protocol is used between a tool (the client) and a language smartness provider (the server) to integrate features like auto complete, go to definition, find all references and alike into the tool

Why?

LSP creates the opportunity to reduce the m-times-n complexity problem of providing a high level of support for any programming language in any editor, IDE, or client endpoint to a simpler m-plus-n problem.


























































GoJavapythonJavaScript
Vim
Emacs
Atom
Sublime
VSCode

For example, when Go came out, plugins were created for each major editor & IDE: Vim, Emacs, Atom, Sublime, VSCode, Eclipse, etc’. Instead of a community effort to create the best code analyzer, the community was focused on creating analyzers for each available tool.

Furthermore, when a new editor is created, it needs to support dozens of languages in order to gain traction - an impossible fit for small projects.

LSP allows language communities to concentrate their efforts on a single, high performing language server, while editor and client communities can concentrate on building a single, high performing, intuitive and idiomatic extension that can communicate with any language server to instantly provide deep language support.

State of LSP

Several companies have come together to support its growth, including Codenvy, Red Hat, Sourcegraph and of course Microsoft.

The protocol is becoming supported by a rapidly growing list of editor and language communities. All popular languages have a language server implementation: C#, Go, Java, JavaScript, python, Swift, C \ C++ and more.

There are already LSP clients for many Editors \ IDE’s: Eclipse Che, VSCode, neovim, Sublime, Atom, Emacs and more.

The quality of the clients & servers is varying, specifically for language clients. VSCode is already using LSP as its backend for language analysis, Neovim is already talking about making LSP a first class citizen, and I believe more will follow.

Further reading

fzf - fuzzy finder on stereoids

Every once in a while I find a new tool that boosts my productivity so much, that I don’t understand how I managed to work without it up to this point.

Today I want to introduce you to a general-purpose command-line fuzzy finder, called fzf -

  • No dependencies.
  • Blazingly fast.
  • Works out of the box, but also extremely configurable.
  • Flexible layout using tmux panes.
  • Batteries included:
    • vim & neovim plugin - I see it as ctrlp.vim on steroids.
    • Key bindings (bash, zsh & fish)
      • CTRL-T paste the selected files and directories onto the command line.
      • CTRL-R paste the selected command from history onto the command line.
      • ALT-C cd into the selected directory.
    • Fuzzy auto-completion for bash, zsh & fish.

But hey, why listen to me when you can just see it in action?