Programming Techniques: Bit hackery

Posted on August 29, 2023 by admin

Sean Eron Anderson (Stanford CS graphics lab)’s bit twiddling pages often shows a bunch of neat bit tricks, but it’s more like a recipe book than a unified way to summarize the common concepts behind them. Here’s my attempt. This page will get updated as I got the time and more useful insights collected.

Concept: Two ways to get two’s complement

This is the basics of most bit hacks below. Sometimes the definition itself is a bit trick on its own.

\begin{align} \overline{-x}+1=x \\ -x = \overline{x}+1 \end{align}

the above reads: to flip sign, flip bits then add one.

\begin{align} \overline{x} = -x-1 \\ \end{align}

the above reads: if you flip the bits, you are getting the negative of it subtracted by 1. e.g. ~4 = -5, ~5 = -6, …, ~(-5) = 4, ~(-4) = 3, …

\begin{align} x = \overline{-x-1} \\ \end{align}

the above reads: any number can be represented by its negative minus -1, then bit-flipped.

\begin{align} \overline{-x} = x-1 \\ -x = \overline{x-1} \end{align}

reads: to flip sign, subtract one first then flip bits

So it means to change signs, you can choose to subtract one first then flip bits or flip bits first then add one.

-x=\overline{x-1} = \overline{x}+1

Let’s try it with 2 instead of 1:

\overline{x-2} = \overline{(x-1)-1} = \overline{x-1}+1 = (\overline{x}+1)+1 = \overline{x}+2

You can generalize it to an arbitrary number by subtracting -1 more under the bar on the left hand side and you will get +1 more on the right hand side. Every extra -1 under the bar (bit flips) shows up as +1 outside the bar (bit flips).

\overline{x-3} = \overline{(x-2)-1} = \overline{x-2}+1 = (\overline{x}+2)+1 = \overline{x}+3

This matches the observation that complement schemes (one’s or two’s) both have increasing magnitude move in opposite directions for positive and negative numbers. Look at this table:

Unsigned	Binary	Two’s Complement
7	111	-1
6	110	-2
5	101	-3
4	100	-4
3	011	3
2	010	2
1	001	1
0	000	0

A very important observation that’d be used over and over blow is that in two’s complement, -1 is always a mask of all binary ‘1’s regardless of the word width.

This rule can also read as: magnitude offsets goes in opposite directions

\begin{align} -x+(n-1)=\overline{x-n} = \overline{x}+n \end{align}

Note that this is NOT distributing bit-flip to two addition/subtraction despite it resembles it with an important distinction that the sign of n changed without turning into (n-1). If it were to distribute, you’ll get (n-2) on the left-hand-side instead of the (n-1) term because the -1 would have been counted twice under distribution.

Bit flips simply doesn’t distribute over the 4 basic (algebraic field) operations. The two’s complement offset is done once and only once when you change the overall representation no matter how many components you break it down into. It’s merely done to shift over the -0 in one’s complement so there’s an extra space for an extra negative number $-2^n$$ which its positive counterpart $+2^n$$ is not representable without starting a new digit.

Note to self: the INT_MIN is just the sign bit of ‘1’ followed by all zeros after.

Concept: XOR can be used for bit flips or check for bit changes

Concept: Top bit holds the sign

Sounds simple, but if you keep in mind that (x<0) is really asking to see if the top bit is 1, you can check if two numbers has opposite signs without bit shifting it down by simply XOR-ing them (anything below the top bit are ignored) and use (x^y)<0 to check for the resulting top bit is 1, which signals that the sign bits are different.

Concept: Sign extensions (the top/sign bit gets drag-copied when right shifted)

When you right shift (in signed integers), the top (sign) bit gets drag-copied (sign extended) by the number of bits you right shifted. (Obviously for signed integers, right shifts are zero-filled)

Can exploit this to

drag the top (sign) bit all the way down to the bottom (so you either get all 1s or 0s) to provide a conditional mask based on the sign (see below)

1??????? \gg 7 \textnormal{ (i.e. type bit width - 1)} = 11111111_2 = -1_{10} \\ 0??????? \gg 7 \textnormal{ (i.e. type bit width - 1)} = 00000000_2 = +0_{10} \\

Signed extensions also means a negative number will stay negative and a positive number will stay positive if you right shift

Sign extension behavior is not guaranteed by 1987 ANSI C, but it’s standard on pretty much anything more modern than that. Just make sure anything that uses this behavior are inlined (so the implementation can be easily swapped out), well documented/commented, and platform checks/switches are in place, and there’s a way to quickly check with the slower but platform independent implementation.

Concept: Getting a bit mask of a 1s (if true) and all 0s (if false)

The ability to convert a logic evaluation (condition) that gives

\begin{align*} 00000001_2 &= +1_{10} & \mathrm{(true)}\\ 00000000_2 &= +0_{10} & \mathrm{(false)} \end{align*}

into a conditional mask that gives

\begin{align*} 11111111_2 &= -1_{10} & \mathrm{(true)}\\ 00000000_2 &= +0_{10} & \mathrm{(false)} \end{align*}

is the basis of many branchless ‘drop/keep this if that’ operations.

This can also be achieved by

putting a minus sign in front, such as -(cond) that will convert a (+1, 0) into (-1, 0), or
more efficiently exploiting sign extensions by dragging the top bit to the bottom (by right shifting by the type’s bit length-1)
computing absolute using the two’s complement’s definition of flip all bits and add 1: drag out a mask that shows that sign, which happens to be a do nothing if all 0s and flip all bits if all 1s in an xor, while the mask of all 1s, which is -1, when subtracted, becomes +1 needed to finish the two’s complement (and that’s subtract by 0 for already positive value).

Concept: $2^n - 1$ sets all binary digits below it to a stream of 1s

When you count binary numbers up, you must exhaust all the lower digits by filling them with all 1s before you get to advance to (set) a new digit on the left of them. For example,

\begin{align*} 1000_2 &= +8_{10}\\ 0111_2 &= +7_{10} \end{align*}

This can be exploited to create bit-masks that preserves all digits on the left of the first ‘1’ seen from the right (LSB), ‘0’ at that lowest (LSB) set bit (aka ‘1’), and all ‘1’s below it.

\begin{align*} 0110,1000_2 &= +104_{10}\\ 0110,0111_2 &= +103_{10} \end{align*}

Binary digits are are the (1 or 0) coefficients of a linear combination of powers of 2. Having a loner ‘1’ (aka everything else is 0) means the number is a power of 2.

Being the lone ‘1’ bit in the number means every bit above it must be zero. Any ‘1’s above the right-most ‘1’ means it’s not the loner, hence not a power of 2.

If you subtract 1 from the power-of-2 number, only all bits below (not including) the line ‘1’ bit becomes 1, and that ‘1’ bit position become zero, and as mentioned before, all bits above it are 0s by definition since the ‘1’ we are working on is a loner.

Since the digits in $2^n$ and $2^n - 1$ are mutually exclusive (see example below)

\begin{align*} 0000,1000_2 &= +8_{10} = 2^3 \\ 0000,0111_2 &= +7_{10} = 2^3 -1 \end{align*}

we can be sure that if we AND them we must get 0 (because one of them has to be zero) and if we XOR them we must get 1. But which one to use?

\begin{align*} 0000,1000_2 &= +8_{10} &=& 2^3 \\ 0000,0111_2 &= +7_{10} &=& 2^3 -1 \\ 0000,1111_2 &= +15_{10} &=& 2^3 \textnormal{ or } (2^3 -1)\\ 0000,1111_2 &= +15_{10} &=& 2^3 \textnormal{ xor } (2^3 -1)\\ 0000,0000_2 &= +0_{10} &=& 2^3 \textnormal{ and } (2^3 -1)\\ \end{align*}

Let’s also check for the non-power of two case

\begin{align*} 0110,1000_2 &= +104_{10}\\ 0110,0111_2 &= +103_{10}\\ 0110,1111_2 &= +111_{10} &=& 104_{10} \textnormal{ or } 103_{10}\\ 0000,1111_2 &= +15_{10} &=& 104_{10} \textnormal{ xor } 103_{10}\\ 0110,0000_2 &= +96_{10} &=& 104_{10} \textnormal{ and } 103_{10}\\ \end{align*}

The xor approach does not work because the upper bits are invariant, so we cannot detect the presence of the upper set bits (upper ‘1’s). It unconditionally gives the same bit pattern (mask) marking the lowest first set bit and everything below it 1s and 0s for everything else above it. Which can be exploited to simplify counting the consecutive trailing zeros (from the right) by turning it into counting the contiguous 1s in this invariant pattern, or add 1 to it and binary search the position of the set bit and subtract 1 because the said bit was made into the invariant (xor) pattern as well so +1 move onto the next upper binary digit.

The or approach detects the presence of the upper set bits but it’s a pain to mask out the invariant lower 1s, which curiously you can do by XOR-ing with the invariant pattern generated by ]latex]2^n \textnormal{ xor } 2^n-1[/latex] or you can do AND-NOT-ing

\begin{align*} 0110,1000_2 &= +104_{10}\\ 0110,0111_2 &= +103_{10}\\ 0110,1111_2 &= +111_{10} &=& 104_{10} \textnormal{ or } 103_{10}\\ 0000,1111_2 &= +15_{10} &=& 104_{10} \textnormal{ xor } 103_{10}\\ 1111,0000_2 &= +240_{10} &=& \overline{104_{10} \textnormal{ xor } 103_{10}}\\ 0110,0000_2 &= +96_{10} &=& (104_{10} \textnormal{ or } 103_{10}) \textnormal{ and } \overline{(104_{10} \textnormal{ xor } 103_{10})}\\ 0110,0000_2 &= +96_{10} &=& (104_{10} \textnormal{ or } 103_{10}) \textnormal{ xor } (104_{10} \textnormal{ xor } 103_{10})\\ 0110,0000_2 &= +96_{10} &=& 104_{10} \textnormal{ and } 103_{10}\\ \end{align*}

Which and happens to already does the job by keeping the top bits (which non-zero value detects their presence) yet unconditionally clear the lowest set bit and everything below it.

The gut of is x & (x-1) maneuver is that it clears the bit from the lowest set bit and everything down below

clearLowestSetBitAndEverythingBelow(x): x & (x-1)

This is used by Brian W. Kernighan to count number of set bits by knocking them one off at a time starting from below. Of course the worst case scenario is when the 1s are so dense that the algorithm must go through every bit without jumping past the zeros.

So the solution is

isPowerOfTwo(x): clearLowestSetBitAndEverythingBelow(x)==0
isPowerOfTwo(x): (x & (x-1))==0

However a special case escaped us, which is x=0. 0x0000 & 0xFFFF is 0, but 0 isn’t a power of 2 unless you consider the minus infinity power which is the territory of floating point anyway. This can be easily patched by making the result unconditionally false if x=0 in the first place.

isPowerOfTwo(x): x && ((x & (x-1))==0)

Note the logical && which means x is first tested for its non-zeroness (by boiling any non-zero value down to +1) and it also enables the efficient short-circuit evaluation which if x is false, which means the result is unconditionally false under &&, the rest are irrelevant so it’s not evaluated.

Concept: Look up table

This is unconditionally the O(1) way because you have a mask of every bit in the type ready and you could index by it. However the penalty is that a load operation could be expensive if not everything can fit in the register file.

Powershell notes (for MATLAB/python users)

Posted on March 28, 2022 by admin

Data Type characteristics

	Powershell	MATLAB	Python
Nearly everything is a/an	Object	Matrix (APL-philosophy)	Object (which are dictionaries)
Assignment behavior*	Reassigned reference	Copy-on-write	Reassigned reference
Monads (wrapper for heterogenous data )	Array/Collections	Cells	Lists

* Shallow assignment (transferring reference only) means the LHS does not have its own copy, so modifying the new reference will modify the underlying data on the RHS.

Syntax / Usage

	Powershell	MATLAB	Python
Method chaining	Yes	Might misbehave	Yes
List Comprehension	–	No. Map first then filter	Yes
Named input arguments	Native `f -a 1 -b 22`	Name-Value pairs parsed inside	Native `f(a=13, b=22)`
Implicit NON-NULL return value	Optional	–	–
Binary map operation	–	Native matrix ops `*fun()` does n-ary	Use numpy `list( map(operator.add, L1, L2) )`
Check Type	`$g -is [type]`	`is*()` or `isa()`	`isinstance(val, type)`
Unpacking (flattening) monads in monads	Default Use unary `,` to avoid	No Use `[{:}]` to perform	No Use , list comp, or `list(itertools.chain(ls))`
Conditional/statement block inside container creation	Yes	–	?
View Object Info with Data	`\| Format-List -Property *` or `Format-List -InputObject`	`properties()` `methods()` `get()`
List members (method and properties)’s prototypes	`\| Get-Member`

Powershell specific

The UNCAPTURED output value in the last line of the block is the return value! Unary side effect statements such as $x++ do not have output value. Watch out for statements that looks like it’s going nowhere at the end of the code as these are not nop/bugs, but return value. This has the same stench as fall-throughs.
foreach() follows the last uncaptured output value return rule above doing a 1-to-1 map from the input collection to output collection (you can assign output to foreach() as it’s also seen as a function)
Powershell suck at binary operations between two arrays. Just an elementwise A+B you’d be thinking in terms of loops and worry about dimensions.
You can put if and loop blocks inside collections list construction, like this:

@( 3, if(cond1){...; $v1}  do{...; $v2}while(cond2) )

MATLAB specific

When used with classes and custom matrices/arrays, chaining fields/properties/methods by indices often do not work, when they do, they often give out only the first element instead of the entire array (IIRC, there are operator methods that needs to be coordinated in the classes involved to make sure they chain correctly). In short, just don’t chain unless in very simple, scalar cases. Always output it to a variable a access the leaf.

Range & Indexing

	Powershell	MATLAB	Python
Logical Indexing	–	Yes	No. Use list comprehension/Numpy
Negative (cyclic) Indexing	Yes	–	Yes
‘`end`‘ of array keyword	–	Yes	No. Skip stop in slice instead
Step (skip every n items)	–	Yes	Yes. Both range or slice
Detect descending range	Yes	–	–
Automatic extend array	–	Yes	–
Reading array out of bounds	Do nothing	Error	Error

Negative (cyclic) indexing along with automatic descending range, along with the lack of ‘end’ keyword is a huge pain in the rear when you want to scan from left to right like A[5:end].

Instead, you’ll have to do $A[4..($A.length-1)] because the range 4..-1 inside A[4..-1] is unrolled as 4,3,2,1,0,-1 (thus scanning from right to left and wraps around) without first consulting with the array A like the end keyword in MATLAB does so it can substitute the ends of the range with the array information before it unrolls.

I am willing to bet that this behavior does not have a sound basis other than people thinking negative indices and descending ranges alone are two good ideas without realizing that nearly nobody freaking wants to scan from right to left and wrap around!

I had the same gripes about negative indices in Python not carefully coordinating with other combinations in common use cases which cases unintuitive behavior.

Range indexing syntax

# Powershell
1..10 # No step/skip for range creation
A[1..10]  # No special treatment in array such as figuring out the 'end'

% MATLAB
A[start:(step):stop]

# Python
A[range(start,stop,step)]
# Slicing (it's not range)
A[(start):(stop):(step)] # Can skip everything 
# In Python, A=X merely reassign the label A as the alias for X.
# Modifying the reassigned A through A=X will modify underlying contents of X
# To deep-copy contents without .Clone(), assign the full slice
A[:] = X

Hasthtable / Dictionaries

% MATLAB: Use dynamic fields in struct or containers.Map()
# Python: dictionaries such as {a:1, b='x'}
# Powershell: @{a=1, b='x'}

Structs

Powershell does not have direct struct or dynamic field name struct. Instead if your object is uniform (you expect the fields not to change much), use [PSCustomObject]@{}. You can also just use simple hashtable @{}, but for some reason it doesn’t work the way I expected when put into arrays when I try to reference it by array index.

Array rules surprises

Array comparisons are filtering operation (not boolean array output like MATLAB). (0..9) -ge 5 gives 5 to 9, not a list of False … False, True … True. To get a boolean array, use this shortcut:

(0..9) | % {$_ -ge 5}

Map-filter combo syntax is | ? instead of Map syntax | %

Monad (Cells in MATLAB) are unpacked and stacked by default (in MATLAB, I had to write a lot of routines to unpack and stack cells of cells). To keep cells packed (in MATLAB lingo, it’s like ‘UniformOutput’, false in cellfun), add a comma unary operator in front of the operation that are expected to be unpacked like this:

.$_.Split('_')

Set Operations

This is one of the WTF moments of Powershell as a programming language. Convenient set operations is essential for most of the routine boring stuff that involves relational data. A lot of Powershell’s intended audience works in database like environment (like IT managers dealing with Active Directory), they have Group-Object for typical data analysis tasks, yet they make life miserable just to do basic set operations like intersection and differencing!

Powershell has a Compare-Object, but this is as unnatural and annoying to use as users are effectively rebuilding all 4 basic set-ops (intersection, union, set-diff, xor) based on any two! Not to mention you have to sift through table to get to the piece you wanted!

Basically Compare-Object out of the box

is a set-diff showing both directions (A\B and also B\A) at the same time. If you throw away the direction info, it’s xor.
if you want intersection, you’ll need to add -IncludeEqual -ExcludeDifferent
(WTF!) If you just specify -ExcludeDifferent, by definition there’s no output because by default Compare-Object shows you ONLY the two set-diffs and you are telling it to not show any diffs!
Union is specifying -IncludeEqual only. But it’d rather stack both then do a | Sort-Object - Unique

Some people might suggest doing | ? {$_ -eq $B} for intersection (or is-member). This is generally a bad idea if you have a lot of data because it’s in the O(n*n) runtime algorithm (loop-within-loop) while any properly done intersection algorithm will just sort then scan the adjacent item to check for duplicates, which gives O(n log(n)) time (typical sorting algorithm takes up most of the time).

If you noticed, it’s set operations within the outputs of Compare-Objects with the Venn diagram of -IncludeEqual -ExcludeDifferent switches! It’s doable, but totally unnecessary mindfuck that should not be repeated frequently.

In MATLAB land, I made my own overloading operators that do set operation over cellstr(), categorical and tabular objects (I went into their code and added the features and talked to TMW so they added the features later), sometimes getting into their sort and indexing logic as necessary. This shows how badly do I need set operations to come naturally.

One might not deal with it too much in low level languages like C++ (STL set doesn’t get used as much compared to other containers), but for a language made to get a lot of common things done (i.e. the language designer kind of reads the users mind), I’m surprised that the Powershell team overlooked the set operations!

Sets are very powerful abstractions that should not be made less descriptive (hard to read) by dancing around it with equivalent operations with some programming gymnastics! If these basic stuff are not built in, we are going to see a lot of people taking ugly shortcuts to avoid coding up these bread and butter functions and put it in libraries (or downloading 3rd-party libraries)!

Powershell surprises

Typical symbolic comparison operators do not work because ‘>’ can be misinterpreted as redirection in command prompts. Use switches like -gt (greater than) instead.
Redirection’s default text output uses UTF16-LE encoding (2 bytes per character). Programs assuming ASCII (1 byte per character) might not behave as intended (e.g. if you use copy command merge an ASCII/UTF8 file with UTF16-LE, you might end up with spaces in the sections that are formatted with UTF16-LE)
Cannot extract string matches from regex without executing a -match which returns boolean unless we use the the $matches$ spilled into variable space. Consider [regex]::Match($Text, $Pattern).Groups[1].Value
Methods are called with parenthesis yet functions are not called with parenthesis, just like cmd-lets! Trying to call a function with multiple input arguments with parenthesis like f(3,5) will be interpreted as calling f with ONE ARGUMENT containing an ARRAY of 3 and 5!
Write-Host takes everything after it literally (white spaces included, almost like echo command), with the exception of plugging in $variables! If you want anything interpreted, such as concatenation, you need to put the bracket around the whole statement!

Libraries and Modules

Reload module using Import-Module $moduleName -Force

GUI Paradigms (1): Redux (Flutter/React) translated to MATLAB

Posted on November 22, 2021 by admin

For GUI development, we often start with controls (or widgets) that user interact with and it’ll emit/run the callback function we registered for the event when the event happens.

Most of the time we just want to read the state/properties of certain controls, process them, and update other controls to show the result. Model-View-Controller (MVC) puts strict boundaries between interaction, data processing and display.

The most common schematic for MVC is a circle showing the cycle of Controller->Model->View, but in practice, it’s the controller that’s the brains. The view can simultaneously accept user interactions, such as a editable text box or a list. The model usually don’t directly update the view directly on its own like the idealized diagram.

MVC with User Action — From https://www.educative.io/blog/mvc-tutorial

With MVC, basically we are concentrating the control’s callbacks to the controller object instead of just letting each control’s callback interact with the data store (model) and view in an unstructured way.

When learning Flutter, I was exposed to the Redux pattern (which came from React). Because the tutorials was designed around the language features of Dart, the documentation kind of obscured the essence of the idea (why do we want to do this) as it dwelt on the framework (structure can be refactored into a package). The docs talked a lot about boundaries but wasn’t clearly why they have to be meticulously observed, which I’ll get to later.

The core inspiration in Redux/BLoC is taking advantage of the concept of ‘listening to a data object for changes’ (instead of UI controls/widget events)!

Instead of having the UI control’s callback directly change other UI control’s state (e.g. for display), we design a state vector/dictionary/struct/class that holds contents (state variables) that we care. It doesn’t have to map 1-1 to input events or 1-1 to output display controls.

When an user interaction (input) event emitted a callback, the control’s callback do whatever it needs to produce the value(s) for the relevant state variable(s) and change the state vector. The changed state vector will trigger the listener that scans for what needs to be updated to reflect the new state and change the states of the appropriate view UI controls.

This way the input UI controls’ callbacks do not have to micromanage what output UI controls to update, so it can focus on the business logic that generates the content pool that will be picked up by the view UI controls to display the results. In Redux, you are free to design your state variables to match more closely to the input data from UI controls or output/view controls’ state. I personally prefer a state vector design that is closer to the output view than input controls.

The intuition above is not the complete/exact Redux, especially with Dart/Flutter/React. We also have to to keep the state in ONE place and make the order of state changes (thus behavior) predictable!

Actions and reducers are separate. Every input control fires a event (action signal) and we’ll wait until the reducers (registered to the actions) to pick it up during dispatch() instead of jumping on it. This way there’s only ONE place that can change states. Leave all the side effects in the control callback where you generate the action. No side effects (like changing other controls) allowed in reducers!
Reducers do not update the state in place (it’s read only). Always generate a new state vector to replace the old one (for performance, we’ll replace the state vector if we verified the contents actually changed). This will make timing predictable (you are stepping through state changes one by one)

In Javascript, there isn’t really a listener actively listening state variable changes. Dispatch (which will be called every time the user interacts using control) just runs through all the listeners registered at the very end after it has dispatched all the reducers. In MATLAB, you can optionally set the state vector to be Observable and attach the change listener callback instead of explicitly calling it within dispatch.

https://gist.github.com/gaearon/ffd88b0e4f00b22c3159

Here is an example of a MATLAB class that captures the spirit of Redux. I added a 2 second delay to emulate long operations and used enableDisableFig() to avoid dealing with queuing user interactions while it’s going through a long operation.

classdef ReduxStoreDemo < handle

    % Should be made private later
    properties (SetAccess = private, SetObservable)
        state % {count}
    end
        
    methods (Static)
        % Made static so reducer cannot call dispatch and indirectly do
        % side effect or create loops
        function state = reducer(state, action)        
            % Can use str2fun(action) here or use a function map
            switch action
                case 'increment'
                    fprintf('Wait 2 secs before incrementing\n');
                    pause(2)
                    state.count = state.count + 1;
                    fprintf('Incremented\n');
            end                
        end        
    end
    
    % We keep all the side-effect generating operations (such as
    % temporarily changing states in the GUI) in dispatch() so
    % there's only ONE PLACE where state can change
    methods
        function dispatch(obj, action, src, evt)
            % Disable all figures during an interaction
            figures = findobj(groot, 'type', 'figure');
            old_fig_states = arrayfun(@(f) enableDisableFig(f, 'off'), figures);      
            src.String = 'Wait ...';
            
                new_state = ReduxStoreDemo.reducer(obj.state, action);
                
                % Don't waste cycles updating nops 
                if( ~isequal(new_state, obj.state) )
                    % MATLAB already have listeners attached.
                    % So no need to scan listeners like React Redux            
                    obj.state = new_state;
                end                
                
            % Re-enable figure obj.controls after it's done
            arrayfun(@(f, os) enableDisableFig(f, os), figures, old_fig_states);                        
            src.String = 'Increment';
        end
    end
    
    methods
        function obj = ReduxStoreDemo()
            figure();            
            obj.state.count = 0;                        
            
            h_1x  = uicontrol('style', 'text', 'String', '1x Box', ...
                              'Units', 'Normalized', ...
                              'Position', [0.1 0.3, 0.2, 0.1], ...
                              'HorizontalAlignment', 'left');                          
            addlistener(obj, 'state', ...
                        'PostSet', @(varargin) obj.update_count_1x( h_1x , varargin{:})); 
                        
            uicontrol('style', 'pushbutton', 'String', 'Increment', ...
                      'Units', 'Normalized', ...
                      'Position', [0.1 0.1, 0.15, 0.1], ...
                      'Callback', @(varargin) obj.dispatch('increment', varargin{:}));                             
            
            % Force trigger the listeners to reflect the initial state
            obj.state = obj.state;
        end
    end
    
    %% These are 'renders' registered when the uiobj.controls are created
    % Should stick to reading off the state. Do not call dispatch here
    % (just leave it for the next action to pick up the consequentials)
    methods
        % The (src, event) is useless for listeners because it's not the 
        % uicontrol handle but the state property's metainfo (access modifiers, etc)
        function update_count_1x(obj, hObj, varargin)            
            hObj.String = num2str(obj.state.count);
        end        
    end
    
end

An easy way to remember Euclid GCD algorithm: laying tiles

Posted on November 21, 2021 by admin

I was a little embarrassed that I’ve never came across Euclid’s GCD algorithm until years after I graduated with Math and Engineering degrees. The descriptions I’ve found online (especially Wikipedia) are convoluted and confusing, and the mechanical description of the algorithm does not shine light to any intuition. Then there comes proofs and abstract algebra properties that even after I followed the reasoning, I’d soon forget after I stop looking at it in a few weeks.

Just by staring at one simple description of the algorithm:

The classic algorithm for computing the GCD, known as Euclid’s algorithm, goes as follows: Let $m$ and $n$ be variables containing the two numbers, divide $m$ by $n$ . Save the divisor in $m$ , and save the remainder in $n$ . If $n$ is $0$ , then stop: $m$ contains the GCD. Otherwise repeat the process, starting with division of $m$ by $n$ .
K.N. King’s C++ Programming (Chapter 6 Exercise 2)

I reversed engineered one line of reasoning how one could come up with the Euclid GCD on his own. Turns out there is one twist/angle that most traditional explanations glossed over: quotients do NOT matter and WHY it does NOT matter!

It goes back to what GCD $(a,b)$ stands for: greatest common divisor. You are looking for the largest factor that simultaneously divides $a$ and $b$ evenly. If you rethink in terms of multiplication, you are finding the biggest tile size $c$ that can simultaneously cover $a$ and $b$ without gaps:

Find $c$ s.t. $a = pc$ and $b= qc$ where $p,q$ are integers.

Imagine you are a lazy and cheap contractor who have unlimited tile samples of all sizes to try before making a large order:

[Goal] you have to cover with two floors with potentially different sizes $a$ and $b$ gaplessly
[Constraint: divisible] your customer won’t let you cut (fractional) tiles because it’s ugly
[Constraint: common denominator] you can only order ONE tile size to take advantage of bulk discounts
[Objective: greatest] more tiles means more work to lay it, so you want to shop for the biggest tile size that does the job.

For simplicity of the argument, we also assume the divisor $b$ is the smaller number. If $b$ is the bigger number, the roles will reverse in the next round because the remainder from dividing by a larger number is the dividend itself, which becomes the divisor in the next round while the old divisor (the larger number) becomes the dividend.

For relatively prime pairs, the algorithm will eventually stop with a GCD of $1$ because $1$ divides all integers.

Here’s the analog of Euclid algorithm:

start out with 1 big tile covering the entire smaller floor $b$
see if we can cover $a$ without gaps using big tiles of size $b$
if yes, we are done. $b$ , the macro-tile is your GCD (perfect-sized tile).
if there are gaps (non-zero remainder), pick a tile-size that covers the ugly gap (the remainder becomes the divisor), then repeat the same process above over the last tile size $b$ (the divisor becomes the dividend) until there are no gaps (remainder become zero).

The algorithm is taking advantage of the fact the remainder is smaller than the last tile size (divisor) so we can rewrite the last tile size in multiples of the remainder (old gap) plus the new gap. By the time the new gap evenly divides the last tile (the big tile right before it), all numbers before that can be written as multiples of the new gap (i.e. the last gap evenly divides all the numbers in the chain all the way up to $b$ and $a$ ).

Let’s start with a simple case GCD $(a=50, b=15)$ that terminates early:

$50 (dividend) = [15+15+15 (divisor)] + 5 (remainder)$

We focus on the last tile $15$ and write it in terms of the old remainder $5$ :

$15 = (5+5+5) + 0$

Since the new remainder is $0$ , the old remainder $5$ divides the last tile $15$ . Since we are dividing $a$ in terms of the remainder $5$ , we have

\begin{aligned} b &= 15 \\ &= (5+5+5) \\ &= 3r \\ \\ a &= 50 \\ & = (15 + 15 + 15) + 5\\ & = 3b + r\\ &= (5+5+5) + (5+5+5) + (5+5+5) + 5\\ &= 3(3r)+r \\ & = 10r \end{aligned}

So both $a$ and $b$ can be written in terms of integer multiples of $r$ right before the algorithm stops.

GCD $(50, 18)$ takes a few more steps:

\begin{aligned} b &= 18\\ a &= 50\\ &= (18 + 18) + 14\\ &=2b + r\\ r &= 14 \\ \\ b_1 &= r = 14\\ a_1 &= b = 18\\ &= (14) + 4\\ &= b_1 + r_1\\ r_1 &= 4\\ \\ b_2 &=r_1 = 4\\ a_2 &= b_1 = 14\\ &= (4+4+4)+2\\ &= 3b_2 + r_2\\ r_2 &= 2\\ \\ b_3 &= r_2 = 2\\ a_3 &= b_2 = 4\\ &=(2+2) + 0\\ r_3 &= 0\\ \end{aligned}

The algorithms stops at $r_3=0$ which means we successfully divided the last tile $a_3$ with $r_2$ (logistically stored in $b_3$ ) with no gaps left. $r_2$ (or $b_3$ is therefore the greatest common factor (divisor) that are shared by all the numbers involved all the way up to $a$ and $b$ .

This is the beauty of Euclid’s GCD algorithm: once the gap (remainder) is sliced small enough to evenly divide the tile (divisor) right before it, every term before it be can written in terms of integer multiples of the last number that divides the last tile without gap (no more remainder).

In our example, $4, 14, 18, 50$ can be written as a multiple of $2$ , aka $r_2$ because integer multiples of numbers that are already integer multiples of $r_2$ can be written in terms of a larger integer multiple of $r_2$ . This is why quotients do not matter in the Euclid GCD algorithm:

\begin{aligned} b_2 &= 2r_2\\ 4 &= (2+2) \\ \\ b_1 &= 3b_2 + r_2\\ &= 3(2r_2) + r_2\\ & = 7r_2\\ 14 &= [(4+4+4)+2] \\ &= [(2+2)+(2+2)+(2+2)+2] \\ \\ b &= b_1 + r_1\\ &=7r_2 + 2r_2\\ &=9r_2\\ 18 &= 14 + 4 \\ &= [(4+4+4)+2] + 4 \\ &= [(2+2)+(2+2)+(2+2)+2]+[(2+2)] \\ \\ a &= 2b + r\\ &=2(9r_2) + 7r_2\\ &= 25r_2\\ 50 & = 18 + 18 + 14 \\ &= [(2+2)+(2+2)+(2+2)+2]+[(2+2)] \cdots \\ &+ [(2+2)+(2+2)+(2+2)+2]+[(2+2)] \cdots \\ &+ [(2+2)+(2+2)+(2+2)+2] \end {aligned}

The spirit of the algorithm is that every time we see a gap, we fill it with a small tile that’s exactly the gap size, and attempt to replace the last tile by covering it in terms of the new smaller tile (that was used to fill the gap). We are recursively slicing the last tile with the gaps produced until there are no gaps left. Once you find the GCD tile, you can replace all the bigger tiles before in terms of it with no gaps.

There’s an interesting perspective of using the Euclid GCD algorithm to solve Diophantine Equations (integer written as a linear combination of integers with integer coefficients): turns if $x=1$ in $c=ax-by$ is the same as writing $a = by+r$ . We can flip the sign of $y$ by saying substituting $y'=-y$ .

In summary,

Euclid GCD’s algorithm is sub-dividing the last (or any one) large tile (last divisor) with the gap (last remainder) until there are no gaps left. Then any bigger tiles up the chain can be expressed as an integer multiple of the last piece (the smallest piece searched so far) that fills the last gap.

The first large tile is of course the smaller of the two numbers involved in the gcd calculation. The larger of the two number is the floor to be covered.

The other observation is that when you see the remainder being 1, you already know the two numbers are relatively prime. The last step to get the remainder to 0 is redundant (because it’s a guaranteed last step).

The other observation is that subdividing the last big tile (divisor) with the last gap (remainder) till it’s evenly divided chains up, because everything is an integer multiple of the smallest piece that evenly divides the gap (remainder) and the last big tile (divisor), therefore the algorithm is recursive.

\gcd(r_1,r_2) = \gcd(r_2, r_3) = ... = \gcd(r_{n-1}, r_n)

But this kind of recursion is not mandatory. It’s a tail recursion* that can be unrolled into iterations (looping), either by the compiler or the programmer, which is what we initially did.

Reading Lambda Calculus

Posted on October 28, 2021 by admin

Complex expressions in lambda calculus notation here is hard to parse in the head correctly until the day I started using Dart Language and noticed the connection between => lambda notation and C-style function layout. Here’s what I learned:

The expressions are right-associative because the right-most expression is the deepest nested function
Function application (feeding values to the arguments) always starts from left-to-right because you can only gain entry to a nest of functions starting from the outermost level, peeling it layer by later like an onion. So if applying arg to statement is denoted by (statement arg), the order of input would be (((statement arg1) arg2) arg3)
Names showing up on the parameter list of the nearest layer sticks to it (local to the function) and excludes everybody else (variable shadowing): this means the same name have absolutely no bearing as a free variable or being a free variable anywhere, so you can (and should) replace it with a unique name.

Here’s the calculus syntax in the book:

This example is the function application used above

Here’s where reusing the variable $x$ in multiple places to mean different things gets confusing as hell, and the author (as well as the nomenclature) do not emphasize the equivalence to variable shadowing rules:

This can be rewritten as having

$\lambda w . w^2$
$\lambda z . (z+1)$
$\lambda f . \lambda g . \lambda x.(f (g x) )$

Upon application,

$((\lambda f . \lambda g . \lambda x.(f \quad (g \quad x) ) \qquad \lambda w . w^2) \qquad \lambda z . (z+1))$

$\implies (\lambda g . \lambda x.(\lambda w . w^2 \qquad (g \quad x) ) \qquad \lambda z . (z+1))$

$\implies \lambda x.(\lambda w . w^2 \qquad (\lambda z . (z+1) \quad x) )$

which clearly reads for an input of $x$ , it’ll be incremented first then squared. Resolving further:

$\implies \lambda x.(\lambda w . w^2 \quad (x+1) )$

$\implies \lambda x.(x+1)^2$

Fucking evils of variable shadowing! Not only it makes the code hard to read and reason, it also make the mathematics hard to follow!

Rambling Nerd with a Plan

Hoi Wong's blog

Category Archives: Computer Science

Programming Techniques: Bit hackery

Concept: Two ways to get two’s complement

Concept: XOR can be used for bit flips or check for bit changes

Concept: Top bit holds the sign

Concept: Sign extensions (the top/sign bit gets drag-copied when right shifted)

Concept: Getting a bit mask of a 1s (if true) and all 0s (if false)

Concept: $2^n - 1$ sets all binary digits below it to a stream of 1s

Concept: Look up table

Powershell notes (for MATLAB/python users)

Data Type characteristics

Syntax / Usage

Range & Indexing

Range indexing syntax

Hasthtable / Dictionaries

Structs

Array rules surprises

Set Operations

Powershell surprises

Libraries and Modules

GUI Paradigms (1): Redux (Flutter/React) translated to MATLAB

An easy way to remember Euclid GCD algorithm: laying tiles

Reading Lambda Calculus

Concept: Two ways to get two’s complement

Concept: XOR can be used for bit flips or check for bit changes

Concept: Top bit holds the sign

Concept: Sign extensions (the top/sign bit gets drag-copied when right shifted)

Concept: Getting a bit mask of a 1s (if true) and all 0s (if false)

Concept: sets all binary digits below it to a stream of 1s

Concept: Look up table

Data Type characteristics

Syntax / Usage

Range & Indexing

Range indexing syntax

Hasthtable / Dictionaries

Structs

Array rules surprises

Set Operations

Powershell surprises

Libraries and Modules

Concept: $2^n - 1$ sets all binary digits below it to a stream of 1s