Fun Exercise Answer

Fun exercise. Try to write this class with no branches. You can add as many classes as you like:

  class Silly { int function (int n) { return n < 5 ? n : 0; } };

-- MichaelFeathers

No branches, polymorphism, library functions, tables, etc. No conditional branches in generated code either.

 #include <stdio.h>                                   
 int sign(int x)                                      
 {                                                    
   int t1,t2;                                        
   t1 =  x >> 31;                                    
   t2 =  -x  ;                                       
   t2 = (unsigned) t2 >> 31;                         
   return   t1  | t2;                                
 }                                                    

 int f(int x)                                         
 {                                                    
  return (sign(sign(5 - x) - 1) + 1) * x;            
 }                                                    

 void main()                                          
 {                                                    
  int i;                                             
  for (i = -2 ; i < 10 ; ++i)                        
    printf("f(%i) = %i\n", i, f(i));  
 }

Object subclass: #Silly instanceVariableNames: classVariableNames: poolDictionaries: ''!

dictionary: anInteger | dictionary | dictionary := Dictionary new. dictionary at: anInteger put: anInteger. 5 to: anInteger do: [ :each | dictionary at: each put: 0]. "ok, I know there might be a branch in #to:do:, but *I* didn't implement it!" ^dictionary! !

function: anInteger ^(self dictionary: anInteger) at: anInteger! !

class Silly { int function (int n) { return n < 5 ? n : 0; } };

becomes:

#include <limits.h>

// using naturals for simplicity. It can be done for the full range

int integers [INT_MAX +1] = { 0, 1, 2, 3, 4, 5 };

class Silly { public: int function (int n) { return integers [n]; } };

Thought: On a machine where pointers and integers are the same size, would there be enough virtual memory for the program after instantiating the integers array?

OK, I just found this Exercise, but you don't rule out language-specific answers, so in C++ I could replace:

class Silly { int function (int n) { return n < 5 ? n : 0; } };

with

class Silly { int function (int n) { return n * (n < 5); } };

The "trick" is that in C and C++, booleans are integers. In my misspent youth I used to use this sort of trick a lot in BASIC, but many BASICs use -1 as TRUE, so a little more math is needed.

If FALSE == 0 and TRUE == -1 (all bits set), as in ForthLanguage, then the trick becomes more efficient:

 : FUNCTION   DUP 5 < AND ;     \ n & ( n < 5 )

or ported back to C:

  class Silly { int function(int n) { return n & -(n < 5); } };

This idiom was published in ThinkingForth, and is probably well known to AssemblyLanguage programmers.

In APL it's such common practice that it doesn't even justify being called a trick. For more type-fascist languages like Java, you'd need to convert the boolean to an int in some other way, say:

 import java.util.*;

 class Silly { 
static Vector v = new Vector(); 
static {
v.addElement(new Boolean(false));
v.addElement(new Boolean(true));
}
int function (int n) { 
return n * v.indexOf(new Boolean(n < 5)) ; 
} 
 }

It may be hubris, but I think this is a "better" solution than the two very memory-intensive attempts above. -- FrankCarver

That IS a nice hack, Frank!

We could do the same in Smalltalk by writing asNumber methods in True and False that return 1 and 0 respectively, and then giving the Silly class the method

 function: n
^n * (n < 5) asNumber

-- RalphJohnson

And that's nice too, Ralph!

Reading the requirements as "Rewrite this class with no branches," is it not unreasonable to take advantage of a branch in an existing, standard class?

Silly { int function (int n) { return Math.min(n, 4); } };

-- DaveSmith

Not quite the same because function(5) = 0. Eeek! No points for me.

 ^(#(0) append: (#(0 1 2 3 4) intersect: (Array with: n))) last

--RonJeffries, who thinks it'd be really neat in APL, but can't remember enough. and good luck trying to typeset APL in a wiki page!

Not wishing to get on my high horse here, but has anyone else applied any XP-style unit tests to this problem? I can't say with surety, as I don't know all the details of all the languages in use, but I can't believe that some of the "solutions" above actually have the same semantics as the original.

Ron's, (just for example, nothing personal) originally had an OffByOne error (it returned 5 rather than 0 for an input of 5) and many of the solutions seem to return 0 or even crash for negatives. I know it's only a "Fun Exercise", but I wouldn't dream of publishing any code without unit testing it. Especially as the original page was all about safe techniques for refactoring. Please prove me wrong.

-- A puzzled FrankCarver

Sorry, Frank, I was just sketching. The code was meant to suggest a solution, not to be one. I misread the spec-code. You're right. Thanks. Still doesn't handle negatives. -- rj

Funny thing about Wiki.. the past comes back to haunt.

only if you are a RecentChangesJunkie. I have a hard time imagining that you surfed back here just in case!

This page was made, what? A year ago? Anyway, I think that Frank's is the most elegant so far. Dave and Ron are cheating terribly by using high level language features. That only means that they will get the job done rather than game around like us. Poor guys :) And Frank is right. The original code allows negatives. Does this mean that source code is a poor UserStory? Or, that people who do puzzles are apt to see things mathematically and assume a domain that is convenient? Probably both. -- MichaelFeathers

For purposes of this exercise, please define "high level language features".

Er, meant to say library things that are not part of the language. For instance, C++ doesn't have "intersect" but its standard library does. You Smalltalk guys seem to think that just because your environment provides things, you should use them. Sheesh. :) -- MichaelFeathers

Another sketch:

 5 to Infinity do: [ :each | Table at: each put: 0].
 MinusInfinity to: 4 do: [ :each | Table at: each put: each].

 Silly>>at: aNumber
^Table at: aNumber

This takes a long time to initialize, but otherwise seems to work fine ...

Let

 zero(x) = 0.
 eq4(x) = { {1,1}, {2,2}, {3,3}, {4,4} }.
 silly(x) = zero(x) + eq4(x).

What language is this?

Being big on tricks with the "sign" function, which returns -1, 0, or 1 depending on the sign of the argument, I'll give an example in everyone's favorite language, VisualBasic:

 Private Function Silly2(n As Integer) As Integer
Silly2 = (Sgn(Sgn(5 - n) - 1) + 1) * n
 End Function

(Yes, I did UnitTest this.)

Normally, I pull dirty tricks like this in SQL (older versions that don't provide DECODE or CASE statements). -- JeffGrigg

Jeff, you are are evil. :) -- mf

Dr. Evil strikes again:

 Private Function Silly3(n As Integer) As Integer
Silly3 = InStr?(Str(n - 5), "-") * n
 End Function

...and you should see what I do with "substring" operations! >;->

A version without tricks. Someone might correct my maths (and I haven't checked this by compiling):

  class Silly {
enum { NUM_NEG_VALUES_IN_INT = MAXINT+1,
NUM_ZERO_VALUES_IN_INT = 1,
NUM_POS_VALUES_IN_INT = MAXINT,
NUM_VALUES_IN_INT = 2*(MAXINT+1) };

char coeff[NUM_VALUES_IN_INT];

Silly() {
memset( coeff,
NUM_NEG_VALUES_IN_INT + NUM_ZERO_VALUES_IN_INT + 4, 1 );
memset( coeff + NUM_NEG_VALUES_IN_INT + NUM_ZERO_VALUES_IN_INT + 4,
NUM_POS_VALUES_IN_INT - 4, 0 );
};

int function (int n) { return n * coeff[ n + NUM_NEG_VALUES_IN_INT ]; };
  };

RichardDevelyn

Most of the solutions above seem to involve branches in non-obvious places, either in built-in language features or in base library implementations. I would really look at the assembler code that is actually executed. I think, the only valid solution would be one that took advantage of the fact that booleans are ints on some low level. Then, a comparison and a multiplication suffice. Otherwise, there will be a branch somewhere. So FrankCarver's first solution is valid and his second isn't. (There will be branches in the implementation of indexof.) Even polymorphic implementations in an OO language will use branches for message dispatch. -- HaskoHeinecke

I agree with the previous statement whole heartedly. Even the statement

 int A =  n<5;

Does on many machine architectures with some compilers result in assembly instructions that are branches. For example it is only on later Intel Chips that the 'set' function is added to the instruction set. Before that time compilers (usually (On all compilers I saw)) generated branches to create the boolean = 1 out of flags set by cmp instructions.

The question remains what the most portable solution?

I offer the following C version while it does not quite fullfill the specification of the class requirement it was hard to test the private member function :).

  #define SIGN_SHFT(n) (sizeof(n)*CHAR_BIT-1)
  #define BRANCHLESS_LE_COMPARE(n1,n2) ((n1 | n1-n2) >> SIGN_SHFT(int n) & 1)
  int function(int n) {  return BRANCHLESS_LE_COMPARE(n,5) * n; }

Note that in the best tradition of obscure C code hacks there are no comments and at least two macros.

As far as I can tell this is portable to ALL two's complement based machines.

-- AlanChristiansen (with alittle help from his friends, below)

Revision History...

The code above used to assume 8 bit bytes... This can't be portable, because it assumes 8-bit-bytes. [....] You wuss. Read X3J11. Read limits.h. CHAR_BIT is your friend. C is the only truly portable language. -- SunirShah

Oh well I did get close, and I was suprised because I was originally sure that sizeof() allowed you to determine the actual number of bits in something I just forgot about CHAR_BIT.

Don't feel bad. Allow me to demonstrate my depravity...

Does the second one of these work? The L to Str stores a binary littele endian version of the long It will surely store 0 2 0 0 for (long)512 The Str to L test for NULL termination!!! So the reverse conversion gives back 0

See PulseLogic for more on these themes.

Here's a RubyLanguage version using polymorphism ...

 class TrueClass?
def n_if_true(n) n end
 end

 class FalseClass?
def n_if_true(n) 0 end
 end

 class Silly2
def f(n)
(n<5).n_if_true(n)
end
 end

And unit test ...

 def test_create
(-100..100). each { |n| 
assert_equal Silly.new.f(n), Silly2.new.f(n)
}
 end

-- JimWeirich

I really like this solution as it is really OO and solves the problem using Classes, not by using a library function or some broken math or implicit casting of boolean to int.

Unfortunately it's not so easy to translate this to Java, because Boolean is final and you can't add methods to existing classes like in Smalltalk.

This works, using an InstanceInitialisationBlock? to make it more interesting:

static interface My {
public int n_if_TRUE_0_if_FALSE(int n);
}

final static Map<Boolean, My> bools = new HashMap<Boolean, My>() {
{
put(Boolean.TRUE, 
new My() { public int n_if_TRUE_0_if_FALSE(int n) { return n; }; });
put(Boolean.FALSE, 
new My() { public int n_if_TRUE_0_if_FALSE(int n) { return 0; }; });
}
};

int eval(boolean b, int n) {
return bools.get(b).n_if_TRUE_0_if_FALSE(n);
}

void test() {
for(int i=-10; i<=10; i++ ) {
System.out.println("i: " + i + " eval: " + eval(i<5,i));
}
}

-- HorstMakitta?

Of course, under appropriate circumstances, you can push this computation to compile-time, and avoid branches by forcing compile-time constants into the run-time executable:

    namespace silly { namespace detail {
        template <int, bool> struct domain         { enum { range = 0 }; }; // OUT-OF-RANGE
        template <int N>     struct domain<N,true> { enum { range = N }; }; // IN-RANGE
    } }

    namespace silly {
        template <int N> struct function {
            enum { value = detail::helper< N, (N < 5) >::value };
        };
    }

and unit test...

    // Compile/link-time conditional checking.
    template <bool> struct static_assert;          // UNIMPLEMENTED for FALSE case.
    template <>     struct static_assert<true> {}; // IMPLEMENTED for TRUE case.

    int main() {
        static_assert< silly::function<-3>::value == -3 >();
        static_assert< silly::function<4>::value == 4>();
        static_assert< silly::function<5>::value == 5>(); // FAILS when uncommented
        static_assert< silly::function<5>::value == 0>(); // SUCCEEDS
    }

-- KevinCousins?.

  #define SIGN_SHFT(n) (sizeof(n)*CHAR_BIT-1)
  #define BRANCHLESS_LE_COMPARE(n1,n2) ((n1 | n1-n2) >> SIGN_SHFT(int n) & 1)
  int function(int n) {  return BRANCHLESS_LE_COMPARE(n,5) * n; }

Here's my version. The operating principle is the truncation-rounding of integer division in C. How I worked out the polynomials is an exercise for the reader. ;) Of course, this won't work for large (in absolute value) n because of integer overflow. You can fix that with some bit-masking hackery (to limit the values) but then you may as well just take the quoted approach.

  int function(int n) { return n * ((26 - 10*n + n*n)/(18 - 8*n + n*n)); }

-- KarlKnechtel

  function :: Num a => a -> Int
  function 1 = 1
  function 2 = 2
  function 3 = 3
  function 4 = 4
  function 5 = 5
  function x = 0

-- MikaelBrockman

What language is that, and in what sense is this not branching? It's HaskellLanguage, and it's not branching because nothing (except for the details of current implementations) says that this function couldn't be compiled into something like FrankCarver's code, and there are no branches in the high-level code.

Without involving a boolean:

 # ruby 
 class Silly
   def function(n)
     a = 5 - n
     b = (a + a.abs)/2      # (n > 5) -> 0
     c = (b/(b - 0.1)).to_i # 0 -> 0, (n != 0) -> 1
     return c * (5-a)
   end
 end

-- MartinDeMello?

The behavior near the INT_MIN boundary gets a little weird, but this handles most cases (nothing like old vanilla C to bend the brain):

   int function(int n)
   {
      return n * ( ((n - 5) < 0) & 1 );
   }

The "& 1" helps just in case the compiler doesn't guarantee (true == 1), though it does assume an odd return. I suppose I could divide:

      return n * ( ((n - 5) < 0) / ((n - 5) < 0) );

Hey! That has an especially obfuse feel to it... -- ChrisFay

Seems to me it has a divide by zero feel to it

Surely the main obstacle is the possibility that 5 - n (or n - 5) causes overflow when evaluated, which would trip up several of the above "tested" solutions.

CategoryCoding