Code puzzle / Computer Science / Forums

Forums

4hv.org :: Forums :: Computer Science

« Previous topic | Next topic »

Code puzzle

Move Thread

LAN_403

Bjørn

Mon Jun 23 2008, 04:25AM

Registered Member #27 Joined: Fri Feb 03 2006, 02:20AM
Location: Hyperborea
Posts: 2058

What does this reverse polish notation algorithm do? Each cell on the stack is 32 bit.

: PUZZLE 
  dup if dup signbit and 
  if abs 0x80000000 else abs 0 endif
  swap dup
  clz dup -rot ++ lsl 9 lsr
  31 rot - 
  127 + 23 lsl
  or or 
  endif ;

------------------------------------------------ ------------------------

Attempt 1, what happens if we run the code with the value 0 loaded on the stack? Every other line is the complete content of the stack and the operator that works on the top cells of the stack. Top of the stack is to the right.

0	
  dup
0 0	
  if
0	
  endif
0	
  ;

We are left with 0 so a no-operation.

That means we can ignore the code that handles the 0 and concentrate on the rest.

: PUZZLE 
  dup signbit and 
  if abs 0x80000000 else abs 0 endif
  swap dup
  clz dup -rot ++ lsl 9 lsr
  31 rot - 
  127 + 23 lsl
  or or 
  ;

------------------------------------------------ ------------------------

Bjørn

Thu Jun 26 2008, 09:21AM

Registered Member #27 Joined: Fri Feb 03 2006, 02:20AM
Location: Hyperborea
Posts: 2058

Attempt 2, what happens if we run the code with the value 1 loaded on the stack?

1
  dup 
1 1
  signbit 
1 1 0x80000000
  and  
1 0
  if 
1
  abs 
1
  #0 
1 0
  endif 
1 0
  swap
0 1
  dup 
0 1 1
  clz  ( count leading zeroes )
0 1 31
  dup 
0 1 31 31
  -rot
0 31 1 31
  ++ 
0 31 1 32
  lsl 
0 31 0
  #9 
0 31 0 9
  lsr
0 31 0 
  #31
0 31 0 31
  rot
0 0 31 31
  -  
0 0 0
  #127
0 0 0 127
  + 
0 0 127
  #23 
0 0 127 23
  lsl 
0 0 1065353216
  or 
0 1065353216
  or  
1065353216
  ;

We end up with 1065353216 or 0x3F800000 in hexadecimal. What is special with that number and what happened to the original 1 since 1065353216 is the constant 127 shifted left by 23?

--------------------------------------------- ---------------------------

Attempt 3, some answers...
If we do a search for 1065353216 we find that it is the decimal value of the 32 bit word that contains the value 1.0 in IEEE 754 floating-point format. In binary 00111111 10000000 00000000 00000000.

If we check the wiki we find the format for 32 bit floating-point numbers:

S EEEEEEEE FFFFFFFFFFFFFFFFFFFFFFF
S - Sign
E - Exponent
F - Fraction

To find out if there is a connection we try with a more substancial number like 754. That gives us 01000100 00111100 10000000 00000000 in binary.

S EEEEEEEE FFFFFFFFFFFFFFFFFFFFFFF
0 10001000 01111001000000000000000

An exponent of 136, since it i biased with 127 we get 136 -127 = 9 as the true exponent. The most significant bits of the fraction is:
011110010
and the binary of 754 is:
1011110010

So that is what happened to the 1 we tried earlier. The most significant bit of any non-zero number is always 1 so there is no point in wasting a bit of storage that can be used to increase precision instead.

The fraction is 23 bit long so to restore the original number we shift it (23 - Exponent) = 14 bits to the right and we get 011110010, we then stick back the implied most significant bit and get 1011110010 which is 754 in decimal.

So the code takes any signed 32 bit integer and converts it to IEEE 754 floating-point format.

Steve Conner

Sat Jun 28 2008, 06:11PM

Registered Member #30 Joined: Fri Feb 03 2006, 10:52AM
Location: Glasgow, Scotland
Posts: 6706

Sorry Dr. Dreadlocks, your puzzle was just too hard.

Bjørn

Sun Jun 29 2008, 01:42PM

Registered Member #27 Joined: Fri Feb 03 2006, 02:20AM
Location: Hyperborea
Posts: 2058

Yo, Dr. Skinhead,

How shall we as humans progress beyond the most basal understanding of our surroundings if we consistently aim for the mediocre? Even the smallest of children understand the basic operations of a stack, everyone should be familiar with the basic arithmetic operations or be able to look them up in their library, some but not all will be familiar with the concept of binary numbers. The rest is just a leap of faith and a determined mind.

Alex

Mon Jun 30 2008, 12:53AM

Geometrically Frustrated
Registered Member #6 Joined: Thu Feb 02 2006, 04:18AM
Location: Bowdoin, Maine
Posts: 373

Damn, I wish I had seen this earlier (or that I hadn't read straight through the answers). Interesting read, though. I have a fondness for RPN; my first programming experiences involved a FORTH-like language.

Steve Conner

Mon Jun 30 2008, 02:49PM

Registered Member #30 Joined: Fri Feb 03 2006, 10:52AM
Location: Glasgow, Scotland
Posts: 6706

Can anyone guess what this one does?

void main(void)
{
   int x;
   float y;

   x = 123456; // assign a value to x
   y = (float)x; // convert x to floating-point
}

Avi

Mon Jun 30 2008, 04:42PM

Registered Member #580 Joined: Mon Mar 12 2007, 03:17PM
Location: Melbourne, Australia
Posts: 410

the same thing as the above one?

Bjørn

Tue Jul 01 2008, 04:24AM

Registered Member #27 Joined: Fri Feb 03 2006, 02:20AM
Location: Hyperborea
Posts: 2058

What it does in detail depends on the compiler and the target. If it is done in Visual C++ 2008 and the target is x86 then it would do the same thing, If the target is a microcontroller it might use a 16 bit int instead of 32 bit and it may use a different floating-point format than IEEE 754 or it may abort the compilation with an error.

Moderator(s): Chris Russell, Noelle, Alex, Tesladownunder, Dave Marshall, Dave Billington, Bjørn, Steve Conner, Wolfram, Kizmo, Mads Barnkob