login  home  contents  what's new  discussion  bug reports     help  links  subscribe  changes  refresh  edit

References to Morton codes (also known as z-order and Lebesgue curves):

fricas
-- i'th group of n bits of h
bits(h,n,i) == And(mask n,shift(h,-n*i))
Type: Void
fricas
-- mix groups of n bits of h with groups of m bits of k
morton(h,n,k,m) ==
 r:SingleInteger:=0
 if n+m > 0 then
   i:=0
   -- stop before fixnum overflow
   while (i+1)*(n+m) <= 29 repeat
     mix:=Or(shift(bits(h,n,i),m),bits(k,m,i))
     r:=Or(r,shift(mix,i*(n+m)))
     i:=i+1
 r
Type: Void
fricas
listHash(l) ==
 r:SingleInteger:=0
 i:=0
 while not empty?(l) repeat
   -- equalize hash weight by number of elements
   r:=morton(r,i,hash first l,1)
   l:=rest l
   i:=i+1
 r
Type: Void

fricas
[hash i for i in 1..5]

\label{eq1}\begin{array}{@{}l}
\displaystyle
\left[{3949119639419317965}, \:{3949065763349535626}, \: \right.
\
\
\displaystyle
\left.{3949083355535587002}, \:{3949029479465804663}, \: \right.
\
\
\displaystyle
\left.{3949047071651856039}\right] 
(1)
Type: List(SingleInteger)
fricas
[morton(0,0,hash i,1) for i in 1..5]
fricas
Compiling function bits with type (NonNegativeInteger,
      NonNegativeInteger,NonNegativeInteger) -> SingleInteger
fricas
Compiling function bits with type (SingleInteger,PositiveInteger,
      NonNegativeInteger) -> SingleInteger
fricas
Compiling function morton with type (NonNegativeInteger,
      NonNegativeInteger,SingleInteger,PositiveInteger) -> 
      SingleInteger

\label{eq2}\left[{52129485}, \:{52108170}, \:{52115130}, \:{52093815}, \:{5
2100775}\right](2)
Type: List(SingleInteger)
fricas
listHash([1])
fricas
Compiling function bits with type (SingleInteger,NonNegativeInteger,
      NonNegativeInteger) -> SingleInteger
fricas
Compiling function morton with type (SingleInteger,
      NonNegativeInteger,SingleInteger,PositiveInteger) -> 
      SingleInteger
fricas
Compiling function listHash with type List(PositiveInteger) -> 
      SingleInteger

\label{eq3}52129485(3)
fricas
matrix [[listHash([i,j]) for j in 1..5] for i in 1..5]

\label{eq4}\left[ 
\begin{array}{ccccc}
{217903347}&{166584550}&{230483430}&{212710839}&{234677431}
\
{115265753}&{63946956}&{127845836}&{110073245}&{132039837}
\
{243063513}&{191744716}&{255643596}&{237871005}&{259837597}
\
{207518331}&{156199534}&{220098414}&{202325823}&{224292415}
\
{251451515}&{200132718}&{264031598}&{246259007}&{268225599}
(4)
Type: Matrix(SingleInteger)
fricas
matrix [[listHash([1,i,j]) for j in 1..5] for i in 1..5]

\label{eq5}\left[ 
\begin{array}{ccccc}
{16519111}&{33034126}&{16293774}&{31235535}&{16289231}
\
{49549141}&{66064156}&{49323804}&{64265565}&{49319261}
\
{16068437}&{32583452}&{15843100}&{30784861}&{15838557}
\
{45951959}&{62466974}&{45726622}&{60668383}&{45722079}
\
{16059351}&{32574366}&{15834014}&{30775775}&{15829471}
(5)
Type: Matrix(SingleInteger)
fricas
matrix [[listHash([2,i,j]) for j in 1..5] for i in 1..5]

\label{eq6}\left[ 
\begin{array}{ccccc}
{82579171}&{99094186}&{82353834}&{97295595}&{82349291}
\
{115609201}&{132124216}&{115383864}&{130325625}&{115379321}
\
{82128497}&{98643512}&{81903160}&{96844921}&{81898617}
\
{112012019}&{128527034}&{111786682}&{126728443}&{111782139}
\
{82119411}&{98634426}&{81894074}&{96835835}&{81889531}
(6)
Type: Matrix(SingleInteger)

Interleave bits by Binary Magic Numbers

This is a fast bit manipulation for combining two hash codes that does not use MOD of a large prime number. Based on the an algorithm by By Sean Eron Anderson.

Ref: http://graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN

spad
)abbrev package MORTON Morton
Morton() : with
    morton2: (SingleInteger,SingleInteger) -> SingleInteger
  == add
-- Shift lower 16 bits of x to even positions of 32 bit word spread(x:SingleInteger):SingleInteger == x := LOGAND(x,65535)$Lisp -- 16rFFFF = 2^16-1 x := LOGAND(LOGIOR(x,ASH(x,8)$Lisp)$Lisp,16711935)$Lisp -- 16r00FF00FF x := LOGAND(LOGIOR(x,ASH(x,4)$Lisp)$Lisp,252645135)$Lisp -- 16r0F0F0F0F x := LOGAND(LOGIOR(x,ASH(x,2)$Lisp)$Lisp,858993459)$Lisp -- 16r33333333 x := LOGAND(LOGIOR(x,ASH(x,1)$Lisp)$Lisp,1431655765)$Lisp -- 16r55555555
-- Interleave bits of x and y so the bits of x are in the odd positions -- and the bits of y are in the even positions of a 29 bit SingleInteger morton2(x:SingleInteger, y:SingleInteger):SingleInteger == LOGAND(LOGIOR(spread y,ASH(spread x,1)$Lisp)$Lisp,536870911)$Lisp -- 16r1FFFFFFF = 2^29 -1
spad
   Compiling FriCAS source code from file 
      /var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/3849729568657923935-25px003.spad
      using old system compiler.
   MORTON abbreviates package Morton 
------------------------------------------------------------------------
   initializing NRLIB MORTON for Morton 
   compiling into NRLIB MORTON 
   compiling local spread : SingleInteger -> SingleInteger
Time: 0 SEC.
compiling exported morton2 : (SingleInteger,SingleInteger) -> SingleInteger Time: 0 SEC.
(time taken in buildFunctor: 0)
;;; *** |Morton| REDEFINED
;;; *** |Morton| REDEFINED Time: 0 SEC.
Cumulative Statistics for Constructor Morton Time: 0 seconds
finalizing NRLIB MORTON Processing Morton for Browser database: --->-->Morton(constructor): Not documented!!!! --->-->Morton((morton2 ((SingleInteger) (SingleInteger) (SingleInteger)))): Not documented!!!! --->-->Morton(): Missing Description ; compiling file "/var/aw/var/LatexWiki/MORTON.NRLIB/MORTON.lsp" (written 31 JUL 2013 03:31:33 PM):
; /var/aw/var/LatexWiki/MORTON.NRLIB/MORTON.fasl written ; compilation finished in 0:00:00.014 ------------------------------------------------------------------------ Morton is now explicitly exposed in frame initial Morton will be automatically loaded when needed from /var/aw/var/LatexWiki/MORTON.NRLIB/MORTON

fricas
matrix [[morton2(hash i,hash j) for j in 1..5] for i in 1..5]

\label{eq7}\left[ 
\begin{array}{ccccc}
{486338803}&{166584550}&{230483430}&{481146295}&{503112887}
\
{383701209}&{63946956}&{127845836}&{378508701}&{400475293}
\
{511498969}&{191744716}&{255643596}&{506306461}&{528273053}
\
{475953787}&{156199534}&{220098414}&{470761279}&{492727871}
\
{519886971}&{200132718}&{264031598}&{514694463}&{536661055}
(7)
Type: Matrix(SingleInteger)




  Subject:   Be Bold !!
  ( 13 subscribers )  
Please rate this page: