Hashtron inference
You are encouraged to solve this task according to the task description, using any language you may know.
Hashtron classifier inference
Description
This task involves implementing a Hashtron classifier inference function. Hashtron classifier program can be machine learned to calculate arbitrary finite computable functions or sets (Given enough CPU time and RAM). The Hashtron classifier takes a command and a number of bits to infer, using a provided program configuration. The inference function for the test will generate a pseudo-random n-bits output. The inference function for the square root demo will generate a square root of a command in range: 0 <= command < 256.
Examples
Test demo
Given the following program configuration and input command:
Program configuration:
Input command:
42
Number of bits:
64
Program:
[[0,2]]
The inference function should process the input and generate the following 64-bit output:
14106184687260844995
Square root demo
Given the following program configuration and input command:
Program configuration:
Input command: A byte (integer) to take square root of.
Number of bits:
4
Program:
[[8776,79884], [12638,1259], [9953,1242], [4658,1228], [5197,1210], [12043,1201], [6892,1183], [7096,1168], [10924,1149], [5551,1136], [5580,1123], [3735,1107], [3652,1091], [12191,1076], [14214,1062], [13056,1045], [14816,1031], [15205,1017], [10736,1001], [9804,989], [13081,974], [6706,960], [13698,944], [14369,928], [16806,917], [9599,906], [9395,897], [4885,883], [10237,870], [10676,858], [18518,845], [2619,833], [13715,822], [11065,810], [9590,799], [5747,785], [2627,776], [8962,764], [5575,750], [3448,738], [5731,725], [9434,714], [3163,703], [3307,690], [3248,678], [3259,667], [3425,657], [3506,648], [3270,639], [3634,627], [3077,617], [3511,606], [27159,597], [27770,589], [28496,580], [28481,571], [29358,562], [31027,552], [30240,543], [30643,534], [31351,527], [31993,519], [32853,510], [33078,502], [33688,495], [29732,487], [29898,480], [29878,474], [26046,468], [26549,461], [28792,453], [26101,446], [32971,439], [29704,432], [23193,426], [29509,421], [27079,415], [32453,409], [24737,404], [25725,400], [23755,395], [52538,393], [53242,386], [19609,380], [26492,377], [24566,358], [31163,368], [57174,363], [26639,364], [31365,357], [60918,350], [21235,338], [28072,322], [28811,314], [27571,320], [17635,309], [51968,169], [54367,323], [60541,254], [26732,270], [52457,157], [27181,276], [19874,227], [22797,320], [59346,271], [25496,260], [54265,231], [22281,250], [42977,318], [26008,240], [87604,142], [94647,314], [52292,157], [20999,216], [89253,316], [22746,29], [68338,312], [22557,317], [110904,104], [70975,285], [51835,277], [51871,313], [132221,228], [18522,290], [68512,285], [118816,302], [150865,268], [68871,273], [68139,290], [84984,285], [150693,266], [396047,272], [84923,269], [215562,258], [68015,248], [247689,235], [214471,229], [264395,221], [263287,212], [280193,201], [108065,194], [263616,187], [148609,176], [263143,173], [378205,162], [312547,154], [50400,147], [328927,140], [279217,132], [181111,127], [672098,118], [657196,113], [459383,111], [833281,105], [520281,102], [755397,95], [787994,91], [492444,82], [1016592,77], [656147,71], [819893,66], [165531,61], [886503,57], [1016551,54], [3547827,49], [14398170,43], [395900,41], [4950628,37], [11481175,33], [100014881,30], [8955328,31], [11313984,27], [13640855,23], [528553762,21], [63483027,17], [952477,8], [950580,4], [918378,2], [918471,1]]
The inference function should process the input and generate the square root of the input byte.
ALGOL 68
In Algol 68, the standard bit manipulation operations are not defined for integers, but for the BITS type. This sample implements operators to handle bit manipulation with integers. These operators also handle bit manipulation with negative numbers - which is not allowed in the standard Algol 68 operators (presumably to avoid getting different results depending on how negative numbers are represented - at the time Algol 68 was defined, two's complement possibly wasn't as universal as it is now).
Because Algol 68 doesn't have unsigned types, integers larger than 64 bits are required. This uses Algol 68G's LONG INT which is 128 bits in version 3 and big enough to hold 35 digits in version 2.
BEGIN # Hashtron Inference - translated from the Go sample #
# operators, modes, etc., to allow bit manipulation on unsigned INT values #
# as Algol 68 doesn't have unsigned integers and we need to have values #
# bigger than 2^63, we use LONG INT (128 bit in Algol 68G) #
# adjust to suit for other implementations #
MODE HINT = LONG INT; # needs to be big enoungh for 2^63 + 1 #
MODE HBIT = LONG BITS;
HBIT b32 = 16rffffffff; # 32-bit mask #
OP TOBITS = ( HINT a )HBIT: IF a >= 0 THEN BIN a ELSE NOT BIN ( - ( a + 1 ) ) FI;
OP TOBITS = ( INT a )HBIT: TOBITS HINT( a );
OP TOINT = ( HBIT a )HINT: IF 1 ELEM a THEN - ( ABS NOT a + 1 ) ELSE ABS a FI;
PRIO ANDAB = 1, ORAB = 1, XORAB = 1;
OP ANDAB = ( REF HINT a, HINT b )REF HINT: a := TOINT ( TOBITS a AND TOBITS b );
OP ANDAB = ( REF HINT a, INT b )REF HINT: a ANDAB HINT( b );
OP ANDAB = ( REF HINT a, HBIT b )REF HINT: a := TOINT ( TOBITS a AND b );
OP ORAB = ( REF HINT a, HINT b )REF HINT: a := TOINT ( TOBITS a OR TOBITS b );
OP XORAB = ( REF HINT a, HINT b )REF HINT: a := TOINT ( TOBITS a XOR TOBITS b );
OP SHL = ( HINT a, INT b )HINT: TOINT ( TOBITS a SHL b );
OP SHL = ( INT a, INT b )HINT: TOINT ( TOBITS HINT( a ) SHL b );
OP SHR = ( HINT a, INT b )HINT: TOINT ( TOBITS a SHR b );
OP OR = ( HINT a, HINT b )HINT: TOINT ( TOBITS a OR TOBITS b );
OP AND = ( HINT a, HBIT b )HINT: TOINT ( TOBITS a AND b );
MODE PGM = STRUCT( INT low, high );
PRIO H = 9;
OP H = ( INT a, b )PGM: ( a, b );
PROC hash = ( HINT n, s, max )HINT:
BEGIN
# Mixing stage, mix input with salt using subtraction #
HINT m := ( n - s ) AND b32;
# Hashing stage, use xor shift with prime coefficients #
m XORAB ( m SHL 2 ) AND b32;
m XORAB ( m SHL 3 ) AND b32;
m XORAB ( m SHR 5 ) AND b32;
m XORAB ( m SHR 7 ) AND b32;
m XORAB ( m SHL 11 ) AND b32;
m XORAB ( m SHL 13 ) AND b32;
m XORAB ( m SHR 17 ) AND b32;
m XORAB ( m SHL 19 ) AND b32;
# Mixing stage 2, mix input with salt using addition #
m +:= s ANDAB b32;
# Modular stage using Lemire's fast alternative to modulo reduction #
( ( m * max ) SHR 32 ) AND b32
END # hash # ;
PROC inference = ( HINT command, INT nbits, []PGM program in )HINT:
IF UPB program in < LWB program in
THEN # the program is empty # 0
ELSE
HINT out := 0;
# Iterate over the bits #
[]PGM program = program in[ AT 0 ];
FOR j FROM 0 TO nbits - 1 DO
HINT input := command OR ( j SHL 16 );
PGM pr0 = program[ 0 ];
HINT ss = low OF pr0;
HINT maxx := high OF pr0;
input := hash( input, ss, maxx );
FOR i FROM 1 TO UPB program DO
PGM pri = program[ i ];
HINT s = low OF pri, max = high OF pri;
maxx -:= max;
input := hash( input, s, maxx )
OD;
input ANDAB 1;
IF input /= 0 THEN
out ORAB 1 SHL j
FI
OD;
out
FI # inference # ;
print( ( "Test Demo: ", whole( inference( 42, 64, 0H2 ), 0 ), newline ) );
[]PGM sq root
= ( 8776H79884, 12638H1259, 9953H1242, 4658H1228, 5197H1210
, 12043H1201, 6892H1183, 7096H1168, 10924H1149, 5551H1136
, 5580H1123, 3735H1107, 3652H1091, 12191H1076, 14214H1062
, 13056H1045, 14816H1031, 15205H1017, 10736H1001, 9804H989
, 13081H974, 6706H960, 13698H944, 14369H928, 16806H917
, 9599H906, 9395H897, 4885H883, 10237H870, 10676H858
, 18518H845, 2619H833, 13715H822, 11065H810, 9590H799
, 5747H785, 2627H776, 8962H764, 5575H750, 3448H738
, 5731H725, 9434H714, 3163H703, 3307H690, 3248H678
, 3259H667, 3425H657, 3506H648, 3270H639, 3634H627
, 3077H617, 3511H606, 27159H597, 27770H589, 28496H580
, 28481H571, 29358H562, 31027H552, 30240H543, 30643H534
, 31351H527, 31993H519, 32853H510, 33078H502, 33688H495
, 29732H487, 29898H480, 29878H474, 26046H468, 26549H461
, 28792H453, 26101H446, 32971H439, 29704H432, 23193H426
, 29509H421, 27079H415, 32453H409, 24737H404, 25725H400
, 23755H395, 52538H393, 53242H386, 19609H380, 26492H377
, 24566H358, 31163H368, 57174H363, 26639H364, 31365H357
, 60918H350, 21235H338, 28072H322, 28811H314, 27571H320
, 17635H309, 51968H169, 54367H323, 60541H254, 26732H270
, 52457H157, 27181H276, 19874H227, 22797H320, 59346H271
, 25496H260, 54265H231, 22281H250, 42977H318, 26008H240
, 87604H142, 94647H314, 52292H157, 20999H216, 89253H316
, 22746H29, 68338H312, 22557H317, 110904H104, 70975H285
, 51835H277, 51871H313, 132221H228, 18522H290, 68512H285
, 118816H302, 150865H268, 68871H273, 68139H290, 84984H285
, 150693H266, 396047H272, 84923H269, 215562H258, 68015H248
, 247689H235, 214471H229, 264395H221, 263287H212, 280193H201
, 108065H194, 263616H187, 148609H176, 263143H173, 378205H162
, 312547H154, 50400H147, 328927H140, 279217H132, 181111H127
, 672098H118, 657196H113, 459383H111, 833281H105, 520281H102
, 755397H95, 787994H91, 492444H82, 1016592H77, 656147H71
, 819893H66, 165531H61, 886503H57, 1016551H54, 3547827H49
, 14398170H43, 395900H41, 4950628H37, 11481175H33, 100014881H30
, 8955328H31, 11313984H27, 13640855H23, 528553762H21, 63483027H17
, 952477H8, 950580H4, 918378H2, 918471H1
);
print( ( newline, "Square root demo for commands in [0..255]:", newline ) );
FOR i FROM 0 TO 255 DO
print( ( whole( inference( i, 4, sq root ), -3 ) ) );
IF ( i + 1 ) MOD 16 = 0 THEN print( ( newline ) ) FI
OD
END- Output:
Test Demo: 14106184687260844995 Square root demo for commands in [0..255]: 0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
C++
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <vector>
uint32_t hash(const uint32_t& number, const uint32_t& salt, const uint32_t& max_value) {
// Mixing stage 1, mix 'number' with 'salt' using subtraction
uint64_t m = ( number - salt ) & 0xFFFFFFFF;
// Hashing stage, use xor shift with prime coefficients
m ^= ( m << 2 ) & 0xFFFFFFFF;
m ^= ( m << 3 ) & 0xFFFFFFFF;
m ^= ( m >> 5 ) & 0xFFFFFFFF;
m ^= ( m >> 7 ) & 0xFFFFFFFF;
m ^= ( m << 11 ) & 0xFFFFFFFF;
m ^= ( m << 13 ) & 0xFFFFFFFF;
m ^= ( m >> 17 ) & 0xFFFFFFFF;
m ^= ( m << 19 ) & 0xFFFFFFFF;
// Mixing stage 2, mix 'number' with 'salt' using addition
m += salt;
m &= 0xFFFFFFFF;
// Modular stage using Lemire's fast alternative to modulo reduction
return ( ( m * max_value ) >> 32 ) & 0xFFFFFFFF;
}
uint64_t inference(const uint32_t& command, const uint32_t& bits, const std::vector<std::vector<uint32_t>>& program) {
uint64_t result = 0;
if ( program.size() == 0 ) {
return result;
}
for ( uint32_t j = 0; j < bits; ++j ) {
uint64_t number = command | ( j << 16 );
const uint32_t salt_1 = program[0][0];
uint32_t max_value = program[0][1];
number = hash(number, salt_1, max_value);
for ( uint32_t i = 1; i < program.size(); ++i ) {
const uint32_t salt_2 = program[i][0];
const uint32_t max = program[i][1];
max_value -= max;
number = hash(number, salt_2, max_value);
}
number &= 1;
if ( number != 0 ) {
result |= ( static_cast<uint64_t>(1) << j );
}
}
return result;
}
int main() {
uint32_t command = 42;
uint32_t bits = 64;
std::vector<std::vector<uint32_t>> program = { { 0, 2 } };
std::cout << "Test demo: " << inference(command, bits, program) << std::endl << std::endl;
bits = 4;
program = {
{ 8776, 79884 }, { 12638, 1259 }, { 9953, 1242 }, { 4658, 1228 }, { 5197, 1210 }, { 12043, 1201 },
{ 6892, 1183 }, { 7096, 1168 }, { 10924, 1149 }, { 5551, 1136 }, { 5580, 1123 }, { 3735, 1107 },
{ 3652, 1091 }, { 12191, 1076 }, { 14214, 1062 }, { 13056, 1045 }, { 14816, 1031 }, { 15205, 1017 },
{ 10736, 1001 }, { 9804, 989 }, { 13081, 974 }, { 6706, 960 }, { 13698, 944 }, { 14369, 928 },
{ 16806, 917 }, { 9599, 906 }, { 9395, 897 }, { 4885, 883 }, { 10237, 870 }, { 10676, 858 },
{ 18518, 845 }, { 2619, 833 }, { 13715, 822 }, { 11065, 810 }, { 9590, 799 }, { 5747, 785 },
{ 2627, 776 }, { 8962, 764 }, { 5575, 750 }, { 3448, 738 }, { 5731, 725 }, { 9434, 714 },
{ 3163, 703 }, { 3307, 690 }, { 3248, 678 }, { 3259, 667 }, { 3425, 657 }, { 3506, 648 },
{ 3270, 639 }, { 3634, 627 }, { 3077, 617 }, { 3511, 606 }, { 27159, 597 }, { 27770, 589 },
{ 28496, 580 }, { 28481, 571 }, { 29358, 562 }, { 31027, 552 }, { 30240, 543 }, { 30643, 534 },
{ 31351, 527 }, { 31993, 519 }, { 32853, 510 }, { 33078, 502 }, { 33688, 495 }, { 29732, 487 },
{ 29898, 480 }, { 29878, 474 }, { 26046, 468 }, { 26549, 461 }, { 28792, 453 }, { 26101, 446 },
{ 32971, 439 }, { 29704, 432 }, { 23193, 426 }, { 29509, 421 }, { 27079, 415 }, { 32453, 409 },
{ 24737, 404 }, { 25725, 400 }, { 23755, 395 }, { 52538, 393 }, { 53242, 386 }, { 19609, 380 },
{ 26492, 377 }, { 24566, 358 }, { 31163, 368 }, { 57174, 363 }, { 26639, 364 }, { 31365, 357 },
{ 60918, 350 }, { 21235, 338 }, { 28072, 322 }, { 28811, 314 }, { 27571, 320 }, { 17635, 309 },
{ 51968, 169 }, { 54367, 323 }, { 60541, 254 }, { 26732, 270 }, { 52457, 157 }, { 27181, 276 },
{ 19874, 227 }, { 22797, 320 }, { 59346, 271 }, { 25496, 260 }, { 54265, 231 }, { 22281, 250 },
{ 42977, 318 }, { 26008, 240 }, { 87604, 142 }, { 94647, 314 }, { 52292, 157 }, { 20999, 216 },
{ 89253, 316 }, { 22746, 29 }, { 68338, 312 }, { 22557, 317 }, { 110904, 104 }, { 70975, 285 },
{ 51835, 277 }, { 51871, 313 }, { 132221, 228 }, { 18522, 290 }, { 68512, 285 }, { 118816, 302 },
{ 150865, 268 }, { 68871, 273 }, { 68139, 290 }, { 84984, 285 }, { 150693, 266 }, { 396047, 272 },
{ 84923, 269 }, { 215562, 258 }, { 68015, 248 }, { 247689, 235 }, { 214471, 229 }, { 264395, 221 },
{ 263287, 212 }, { 280193, 201 }, { 108065, 194 }, { 263616, 187 }, { 148609, 176 }, { 263143, 173 },
{ 378205, 162 }, { 312547, 154 }, { 50400, 147 }, { 328927, 140 }, { 279217, 132 }, { 181111, 127 },
{ 672098, 118 }, { 657196, 113 }, { 459383, 111 }, { 833281, 105 }, { 520281, 102 }, { 755397, 95 },
{ 787994, 91 }, { 492444, 82 }, { 1016592, 77 }, { 656147, 71 }, { 819893, 66 }, { 165531, 61 },
{ 886503, 57 }, { 1016551, 54 }, { 3547827, 49 }, { 14398170, 43 }, { 395900, 41 }, { 4950628, 37 },
{ 11481175, 33 }, { 100014881, 30 }, { 8955328, 31 }, { 11313984, 27 }, { 13640855, 23 },
{ 528553762, 21 }, { 63483027, 17 }, { 952477, 8 }, { 950580, 4 }, {918378, 2 }, { 918471, 1 }
};
std::cout << "Square root demo for commands in 0..255:" << std::endl;
for ( command = 0; command < 256; ++command ) {
std::cout << std::setw(2) << inference(command, bits, program) << ( ( command % 16 == 15 ) ? "\n" : " " );
}
}
- Output:
Test demo: 14106184687260844995 Square root demo for commands in 0..255: 0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
FreeBASIC
Function Hashtron(n As Ulongint, s As Ulongint, max As Ulongint) As Ulongint
Dim As Ulongint U32 = &hFFFFFFFF
' Mixing stage, mix input with salt using subtraction
Dim As Ulongint m = (n - s) And U32
' Hashing stage, use xor shift with prime coefficients
m Xor= ((m Shl 2) And U32)
m Xor= ((m Shl 3) And U32)
m Xor= ((m Shr 5) And U32)
m Xor= ((m Shr 7) And U32)
m Xor= ((m Shl 11) And U32)
m Xor= ((m Shl 13) And U32)
m Xor= ((m Shr 17) And U32)
m Xor= ((m Shl 19) And U32)
' Mixing stage 2, mix input with salt using addition
m = (m + s) And U32
' Modular stage using Lemire's fast alternative to modulo reduction
Return ((m * max) Shr 32) 'And U32
End Function
Function Inference(cmd As Integer, bits As Integer, program() As Ulong) As Ulongint
Dim As Ulongint salida = 0
If Ubound(program) Then
' Iterate over the bits
For j As Integer = 0 To bits - 1
Dim As Integer ss = program(0, 0)
Dim As Integer maxx = program(0, 1)
Dim As Integer entrada = cmd Or (j Shl 16)
entrada = Hashtron(entrada, ss, maxx)
For i As Integer = 1 To Ubound(program, 1)
maxx -= program(i+1)
entrada = Hashtron(entrada, program(i), maxx)
Next i
If entrada Mod 2 <> 0 Then salida Or= (1 Shl j)
Next j
End If
Return salida
End Function
Dim As Ulong program(1) = {0, 2}
Print "Test demo:"
Print Inference(42, 64, program())
Dim As Ulong program2(255, 1) = { _
{8776,79884}, {12638,1259}, {9953,1242}, {4658,1228}, {5197,1210}, {12043,1201}, _
{6892,1183}, {7096,1168}, {10924,1149}, {5551,1136}, {5580,1123}, {3735,1107}, _
{3652,1091}, {12191,1076}, {14214,1062}, {13056,1045}, {14816,1031}, {15205,1017}, _
{10736,1001}, {9804,989}, {13081,974}, {6706,960}, {13698,944}, {14369,928}, _
{16806,917}, {9599,906}, {9395,897}, {4885,883}, {10237,870}, {10676,858}, _
{18518,845}, {2619,833}, {13715,822}, {11065,810}, {9590,799}, {5747,785}, _
{2627,776}, {8962,764}, {5575,750}, {3448,738}, {5731,725}, {9434,714}, _
{3163,703}, {3307,690}, {3248,678}, {3259,667}, {3425,657}, {3506,648}, _
{3270,639}, {3634,627}, {3077,617}, {3511,606}, {27159,597}, {27770,589}, _
{28496,580}, {28481,571}, {29358,562}, {31027,552}, {30240,543}, {30643,534}, _
{31351,527}, {31993,519}, {32853,510}, {33078,502}, {33688,495}, {29732,487}, _
{29898,480}, {29878,474}, {26046,468}, {26549,461}, {28792,453}, {26101,446}, _
{32971,439}, {29704,432}, {23193,426}, {29509,421}, {27079,415}, {32453,409}, _
{24737,404}, {25725,400}, {23755,395}, {52538,393}, {53242,386}, {19609,380}, _
{26492,377}, {24566,358}, {31163,368}, {57174,363}, {26639,364}, {31365,357}, _
{60918,350}, {21235,338}, {28072,322}, {28811,314}, {27571,320}, {17635,309}, _
{51968,169}, {54367,323}, {60541,254}, {26732,270}, {52457,157}, {27181,276}, _
{19874,227}, {22797,320}, {59346,271}, {25496,260}, {54265,231}, {22281,250}, _
{42977,318}, {26008,240}, {87604,142}, {94647,314}, {52292,157}, {20999,216}, _
{89253,316}, {22746,29}, {68338,312}, {22557,317}, {110904,104}, {70975,285}, _
{51835,277}, {51871,313}, {132221,228}, {18522,290}, {68512,285}, {118816,302}, _
{150865,268}, {68871,273}, {68139,290}, {84984,285}, {150693,266}, {396047,272}, _
{84923,269}, {215562,258}, {68015,248}, {247689,235}, {214471,229}, {264395,221}, _
{263287,212}, {280193,201}, {108065,194}, {263616,187}, {148609,176}, {263143,173}, _
{378205,162}, {312547,154}, {50400,147}, {328927,140}, {279217,132}, {181111,127}, _
{672098,118}, {657196,113}, {459383,111}, {833281,105}, {520281,102}, {755397,95}, _
{787994,91}, {492444,82}, {1016592,77}, {656147,71}, {819893,66}, {165531,61}, _
{886503,57}, {1016551,54}, {3547827,49}, {14398170,43}, {395900,41}, {4950628,37}, _
{11481175,33}, {100014881,30}, {8955328,31}, {11313984,27}, {13640855,23}, _
{528553762,21}, {63483027,17}, {952477,8}, {950580,4}, {918378,2}, {918471,1} }
Print !"\nSquare root demo for commands in (0, 255):"
Dim As Ulong results(255)
For i As Uinteger = 0 To 255
results(i) = Inference(i, 4, program2())
Next i
For i As Uinteger = 0 To 255
Print Using "###"; Inference(i, 4, program2());
If (i+1) Mod 16 = 0 Then Print
Next i
Sleep
- Output:
Test demo: 14106184687260844995 Square root demo for commands in (0, 255): 0 0 10 15 7 0 5 10 2 9 5 10 7 10 4 14 14 13 13 13 10 9 5 4 14 3 5 15 10 5 4 4 12 13 1 12 8 0 8 15 5 10 4 9 11 10 15 2 14 7 7 13 8 11 4 14 2 10 10 9 9 6 4 13 13 7 13 8 6 9 15 15 5 11 7 13 11 3 15 5 1 0 6 3 12 14 13 9 10 11 14 13 8 4 5 3 13 10 8 14 14 3 8 4 9 12 8 3 6 6 1 10 15 6 10 6 9 6 3 10 5 7 10 6 13 6 3 1 7 11 1 9 13 15 7 15 12 1 7 7 4 13 15 9 15 8 2 5 7 10 3 11 0 9 10 11 9 10 14 15 4 10 3 13 3 11 9 10 7 14 11 15 7 9 10 5 8 15 3 5 15 8 5 10 12 15 15 7 13 14 10 14 1 1 9 14 10 6 5 14 1 15 15 9 14 9 2 10 11 13 7 12 15 1 7 3 15 15 4 9 2 5 7 1 15 14 14 10 15 1 13 10 6 9 5 0 11 14 9 1 13 6 6 6 8 13 13 8 13 10 14 14 15 1 7 10
Go
package main
func Inference(command uint32, bits byte, program [][2]uint32) (out uint64) {
// Check if the program is empty
if len(program) == 0 {
return
}
// Iterate over the bits
for j := byte(0); j < bits; j++ {
var input = command | (uint32(j) << 16)
var ss, maxx = program[0][0], program[0][1]
input = Hash(input, ss, maxx)
for i := 1; i < len(program); i++ {
var s, max = program[i][0], program[i][1]
maxx -= max
input = Hash(input, s, maxx)
}
input &= 1
if input != 0 {
out |= 1 << j
}
}
return
}
func Hash(n uint32, s uint32, max uint32) uint32 {
// Mixing stage, mix input with salt using subtraction
var m = n - s
// Hashing stage, use xor shift with prime coefficients
m ^= m << 2
m ^= m << 3
m ^= m >> 5
m ^= m >> 7
m ^= m << 11
m ^= m << 13
m ^= m >> 17
m ^= m << 19
// Mixing stage 2, mix input with salt using addition
m += s
// Modular stage using Lemire's fast alternative to modulo reduction
return uint32((uint64(m) * uint64(max)) >> 32)
}
func main() {
println(Inference(42, 64, [][2]uint32{{0, 2}}))
}
https://go.dev/play/p/AsmOzKWx7jB
- Output:
14106184687260844995 0 0 1 1 2 1 3 1 4 2 5 2 6 2 7 2 8 2 9 3 10 3 11 3 12 3 13 3 14 3 15 3 16 4 17 4 18 4 19 4 20 4 21 4 22 4 23 4 24 4 25 5 26 5 27 5 28 5 29 5 30 5 31 5 32 5 33 5 34 5 35 5 36 6 37 6 38 6 39 6 40 6 41 6 42 6 43 6 44 6 45 6 46 6 47 6 48 6 49 7 50 7 51 7 52 7 53 7 54 7 55 7 56 7 57 7 58 7 59 7 60 7 61 7 62 7 63 7 64 8 65 8 66 8 67 8 68 8 69 8 70 8 71 8 72 8 73 8 74 8 75 8 76 8 77 8 78 8 79 8 80 8 81 9 82 9 83 9 84 9 85 9 86 9 87 9 88 9 89 9 90 9 91 9 92 9 93 9 94 9 95 9 96 9 97 9 98 9 99 9 100 10 101 10 102 10 103 10 104 10 105 10 106 10 107 10 108 10 109 10 110 10 111 10 112 10 113 10 114 10 115 10 116 10 117 10 118 10 119 10 120 10 121 11 122 11 123 11 124 11 125 11 126 11 127 11 128 11 129 11 130 11 131 11 132 11 133 11 134 11 135 11 136 11 137 11 138 11 139 11 140 11 141 11 142 11 143 11 144 12 145 12 146 12 147 12 148 12 149 12 150 12 151 12 152 12 153 12 154 12 155 12 156 12 157 12 158 12 159 12 160 12 161 12 162 12 163 12 164 12 165 12 166 12 167 12 168 12 169 13 170 13 171 13 172 13 173 13 174 13 175 13 176 13 177 13 178 13 179 13 180 13 181 13 182 13 183 13 184 13 185 13 186 13 187 13 188 13 189 13 190 13 191 13 192 13 193 13 194 13 195 13 196 14 197 14 198 14 199 14 200 14 201 14 202 14 203 14 204 14 205 14 206 14 207 14 208 14 209 14 210 14 211 14 212 14 213 14 214 14 215 14 216 14 217 14 218 14 219 14 220 14 221 14 222 14 223 14 224 14 225 15 226 15 227 15 228 15 229 15 230 15 231 15 232 15 233 15 234 15 235 15 236 15 237 15 238 15 239 15 240 15 241 15 242 15 243 15 244 15 245 15 246 15 247 15 248 15 249 15 250 15 251 15 252 15 253 15 254 15 255 15
Java
public class Main {
public static long inference(int command, int bits, int[][] program) {
long out = 0;
// Check if the program is empty
if ( program.length == 0 ) {
return out;
}
// Iterate over the bits
for ( int j = 0; j < bits; j++ ) {
int input = command | ( j << 16);
int ss = program[0][0];
int maxx = program[0][1];
input = hash(input, ss, maxx);
for ( int i = 1; i < program.length; i++ ) {
int s = program[i][0];
int max = program[i][1];
maxx -= max;
input = hash(input, s, maxx);
}
input &= 1;
if (input != 0) {
out |= (long)1 << (long) j;
}
}
return out;
}
public static int hash(int n, int s, int max_val) {
// Mixing stage, mix input with salt using subtraction
long m = (n - s) & 0xFFFFFFFFL;
// Hashing stage, use xor shift with prime coefficients
m ^= (m << 2) & 0xFFFFFFFFL;
m ^= (m << 3) & 0xFFFFFFFFL;
m ^= (m >> 5) & 0xFFFFFFFFL;
m ^= (m >> 7) & 0xFFFFFFFFL;
m ^= (m << 11) & 0xFFFFFFFFL;
m ^= (m << 13) & 0xFFFFFFFFL;
m ^= (m >> 17) & 0xFFFFFFFFL;
m ^= (m << 19) & 0xFFFFFFFFL;
// Mixing stage 2, mix input with salt using addition
m += s;
m &= 0xFFFFFFFFL;
// Modular stage using Lemire's fast alternative to modulo reduction
return (int) ( ( ( m * max_val ) >>> 32 ) & 0xFFFFFFFFL );
}
public static void main(String[] args) {
int command = 42;
int[][] program = { { 0, 2 } }; // Example program
int bits = 64;
long result = inference(command, bits, program);
System.out.println(Long.toUnsignedString(result));
}
}
Both Demos
public final class HashtronInference {
public static void main(String[] args) {
int command = 42;
int bits = 64;
int[][] program = { { 0, 2 } };
long result = inference(command, bits, program);
System.out.println("Test demo: " + Long.toUnsignedString(result));
System.out.println();
bits = 4;
program = new int[][] {
{ 8776, 79884 }, { 12638, 1259 }, { 9953, 1242 }, { 4658, 1228 }, { 5197, 1210 }, { 12043, 1201 },
{ 6892, 1183 }, { 7096, 1168 }, { 10924, 1149 }, { 5551, 1136 }, { 5580, 1123 }, { 3735, 1107 },
{ 3652, 1091 }, { 12191, 1076 }, { 14214, 1062 }, { 13056, 1045 }, { 14816, 1031 }, { 15205, 1017 },
{ 10736, 1001 }, { 9804, 989 }, { 13081, 974 }, { 6706, 960 }, { 13698, 944 }, { 14369, 928 },
{ 16806, 917 }, { 9599, 906 }, { 9395, 897 }, { 4885, 883 }, { 10237, 870 }, { 10676, 858 },
{ 18518, 845 }, { 2619, 833 }, { 13715, 822 }, { 11065, 810 }, { 9590, 799 }, { 5747, 785 },
{ 2627, 776 }, { 8962, 764 }, { 5575, 750 }, { 3448, 738 }, { 5731, 725 }, { 9434, 714 },
{ 3163, 703 }, { 3307, 690 }, { 3248, 678 }, { 3259, 667 }, { 3425, 657 }, { 3506, 648 },
{ 3270, 639 }, { 3634, 627 }, { 3077, 617 }, { 3511, 606 }, { 27159, 597 }, { 27770, 589 },
{ 28496, 580 }, { 28481, 571 }, { 29358, 562 }, { 31027, 552 }, { 30240, 543 }, { 30643, 534 },
{ 31351, 527 }, { 31993, 519 }, { 32853, 510 }, { 33078, 502 }, { 33688, 495 }, { 29732, 487 },
{ 29898, 480 }, { 29878, 474 }, { 26046, 468 }, { 26549, 461 }, { 28792, 453 }, { 26101, 446 },
{ 32971, 439 }, { 29704, 432 }, { 23193, 426 }, { 29509, 421 }, { 27079, 415 }, { 32453, 409 },
{ 24737, 404 }, { 25725, 400 }, { 23755, 395 }, { 52538, 393 }, { 53242, 386 }, { 19609, 380 },
{ 26492, 377 }, { 24566, 358 }, { 31163, 368 }, { 57174, 363 }, { 26639, 364 }, { 31365, 357 },
{ 60918, 350 }, { 21235, 338 }, { 28072, 322 }, { 28811, 314 }, { 27571, 320 }, { 17635, 309 },
{ 51968, 169 }, { 54367, 323 }, { 60541, 254 }, { 26732, 270 }, { 52457, 157 }, { 27181, 276 },
{ 19874, 227 }, { 22797, 320 }, { 59346, 271 }, { 25496, 260 }, { 54265, 231 }, { 22281, 250 },
{ 42977, 318 }, { 26008, 240 }, { 87604, 142 }, { 94647, 314 }, { 52292, 157 }, { 20999, 216 },
{ 89253, 316 }, { 22746, 29 }, { 68338, 312 }, { 22557, 317 }, { 110904, 104 }, { 70975, 285 },
{ 51835, 277 }, { 51871, 313 }, { 132221, 228 }, { 18522, 290 }, { 68512, 285 }, { 118816, 302 },
{ 150865, 268 }, { 68871, 273 }, { 68139, 290 }, { 84984, 285 }, { 150693, 266 }, { 396047, 272 },
{ 84923, 269 }, { 215562, 258 }, { 68015, 248 }, { 247689, 235 }, { 214471, 229 }, { 264395, 221 },
{ 263287, 212 }, { 280193, 201 }, { 108065, 194 }, { 263616, 187 }, { 148609, 176 }, { 263143, 173 },
{ 378205, 162 }, { 312547, 154 }, { 50400, 147 }, { 328927, 140 }, { 279217, 132 }, { 181111, 127 },
{ 672098, 118 }, { 657196, 113 }, { 459383, 111 }, { 833281, 105 }, { 520281, 102 }, { 755397, 95 },
{ 787994, 91 }, { 492444, 82 }, { 1016592, 77 }, { 656147, 71 }, { 819893, 66 }, { 165531, 61 },
{ 886503, 57 }, { 1016551, 54 }, { 3547827, 49 }, { 14398170, 43 }, { 395900, 41 }, { 4950628, 37 },
{ 11481175, 33 }, { 100014881, 30 }, { 8955328, 31 }, { 11313984, 27 }, { 13640855, 23 },
{ 528553762, 21 }, { 63483027, 17 }, { 952477, 8 }, { 950580, 4 }, {918378, 2 }, { 918471, 1 }
};
System.out.println("Square root demo for commands in 0..255:");
for ( command = 0; command < 256; command++ ) {
System.out.print(
String.format("%2d%s", inference(command, bits, program), ( command % 16 == 15 ) ? "\n" : " " ));
}
}
public static long inference(int command, int bits, int[][] program) {
long result = 0;
if ( program.length == 0 ) {
return result;
}
for ( int j = 0; j < bits; j++ ) {
int number = command | ( j << 16 );
final int saltOne = program[0][0];
int maxValue = program[0][1];
number = hash(number, saltOne, maxValue);
for ( int i = 1; i < program.length; i++ ) {
final int saltTwo = program[i][0];
final int max = program[i][1];
maxValue -= max;
number = hash(number, saltTwo, maxValue);
}
number &= 1;
if ( number != 0 ) {
result |= ( 1L << j );
}
}
return result;
}
public static int hash(int number, int salt, int maxValue) {
// Mixing stage 1, mix 'number' with 'salt' using subtraction
long m = ( number - salt ) & 0xFFFFFFFFL;
// Hashing stage, use xor shift with prime coefficients
m ^= ( m << 2 ) & 0xFFFFFFFFL;
m ^= ( m << 3 ) & 0xFFFFFFFFL;
m ^= ( m >> 5 ) & 0xFFFFFFFFL;
m ^= ( m >> 7 ) & 0xFFFFFFFFL;
m ^= ( m << 11 ) & 0xFFFFFFFFL;
m ^= ( m << 13 ) & 0xFFFFFFFFL;
m ^= ( m >> 17 ) & 0xFFFFFFFFL;
m ^= ( m << 19 ) & 0xFFFFFFFFL;
// Mixing stage 2, mix 'number' with 'salt' using addition
m += salt;
m &= 0xFFFFFFFFL;
// Modular stage using Lemire's fast alternative to modulo reduction
return (int) ( ( ( m * maxValue ) >>> 32 ) & 0xFFFFFFFFL );
}
}
- Output:
Test demo: 14106184687260844995 Square root demo for commands in 0..255: 0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
Julia
function hash(n, s, max_val)
# Mixing stage, mix input with salt using subtraction
m = (n - s) & 0xFFFFFFFF
# Hashing stage, use xor shift with prime coefficients
m ⊻= (m << 2) & 0xFFFFFFFF
m ⊻= (m << 3) & 0xFFFFFFFF
m ⊻= (m >> 5) & 0xFFFFFFFF
m ⊻= (m >> 7) & 0xFFFFFFFF
m ⊻= (m << 11) & 0xFFFFFFFF
m ⊻= (m << 13) & 0xFFFFFFFF
m ⊻= (m >> 17) & 0xFFFFFFFF
m ⊻= (m << 19) & 0xFFFFFFFF
# Mixing stage 2, mix input with salt using addition
m += s
m &= 0xFFFFFFFF
# Modular stage using Lemire's fast alternative to modulo reduction
return ((m * max_val) >> 32) & 0xFFFFFFFF
end
function inference(command, bits, program)
out = UInt(0)
# Check if the program is empty
length(program) == 0 && return out
# Iterate over the bits
for j in 0:bits-1
input_val = command | (j << 16)
ss, maxx = program[begin]
input_val = hash(input_val, ss, maxx)
for i in firstindex(program)+1:lastindex(program)
s, max_val = program[i]
maxx -= max_val
input_val = hash(input_val, s, maxx)
end
if isodd(input_val)
out |= 1 << j
end
end
return out
end
println(inference(42, 64, [[0, 2]]))
for i in 0x0:0xff
println(i, " ", inference(i, 4, [
[8776, 79884], [12638, 1259], [9953, 1242], [4658, 1228], [5197, 1210], [12043, 1201],
[6892, 1183], [7096, 1168], [10924, 1149], [5551, 1136], [5580, 1123], [3735, 1107],
[3652, 1091], [12191, 1076], [14214, 1062], [13056, 1045], [14816, 1031], [15205, 1017],
[10736, 1001], [9804, 989], [13081, 974], [6706, 960], [13698, 944], [14369, 928],
[16806, 917], [9599, 906], [9395, 897], [4885, 883], [10237, 870], [10676, 858],
[18518, 845], [2619, 833], [13715, 822], [11065, 810], [9590, 799], [5747, 785],
[2627, 776], [8962, 764], [5575, 750], [3448, 738], [5731, 725], [9434, 714],
[3163, 703], [3307, 690], [3248, 678], [3259, 667], [3425, 657], [3506, 648],
[3270, 639], [3634, 627], [3077, 617], [3511, 606], [27159, 597], [27770, 589],
[28496, 580], [28481, 571], [29358, 562], [31027, 552], [30240, 543], [30643, 534],
[31351, 527], [31993, 519], [32853, 510], [33078, 502], [33688, 495], [29732, 487],
[29898, 480], [29878, 474], [26046, 468], [26549, 461], [28792, 453], [26101, 446],
[32971, 439], [29704, 432], [23193, 426], [29509, 421], [27079, 415], [32453, 409],
[24737, 404], [25725, 400], [23755, 395], [52538, 393], [53242, 386], [19609, 380],
[26492, 377], [24566, 358], [31163, 368], [57174, 363], [26639, 364], [31365, 357],
[60918, 350], [21235, 338], [28072, 322], [28811, 314], [27571, 320], [17635, 309],
[51968, 169], [54367, 323], [60541, 254], [26732, 270], [52457, 157], [27181, 276],
[19874, 227], [22797, 320], [59346, 271], [25496, 260], [54265, 231], [22281, 250],
[42977, 318], [26008, 240], [87604, 142], [94647, 314], [52292, 157], [20999, 216],
[89253, 316], [22746, 29], [68338, 312], [22557, 317], [110904, 104], [70975, 285],
[51835, 277], [51871, 313], [132221, 228], [18522, 290], [68512, 285], [118816, 302],
[150865, 268], [68871, 273], [68139, 290], [84984, 285], [150693, 266], [396047, 272],
[84923, 269], [215562, 258], [68015, 248], [247689, 235], [214471, 229], [264395, 221],
[263287, 212], [280193, 201], [108065, 194], [263616, 187], [148609, 176], [263143, 173],
[378205, 162], [312547, 154], [50400, 147], [328927, 140], [279217, 132], [181111, 127],
[672098, 118], [657196, 113], [459383, 111], [833281, 105], [520281, 102], [755397, 95],
[787994, 91], [492444, 82], [1016592, 77], [656147, 71], [819893, 66], [165531, 61],
[886503, 57], [1016551, 54], [3547827, 49], [14398170, 43], [395900, 41], [4950628, 37],
[11481175, 33], [100014881, 30], [8955328, 31], [11313984, 27], [13640855, 23],
[528553762, 21], [63483027, 17], [952477, 8], [950580, 4], [918378, 2], [918471, 1],
]))
end
- Output:
Same as Go example.
Phix
This sort of thing is generally quite painful in Phix, since it will insist on things like zero minus one being -1 rather than some huge positive number... you certainly have to take some care it always uses unsigned masking, especially since Phix doesn't really have any such thing as unsigned ints.
requires(64)
constant U32 = #FFFFFFFF
function hashtron(integer n, s, mx)
// Mixing stage, mix input with salt using subtraction
atom m = (n-s) && U32
// Hashing stage, use xor shift with prime coefficients
for p in {-2,-3,+5,+7,-11,-13,+17,-19} do
m = xor_bitsu(m,shift_bits(m,p) && U32)
end for
// Mixing stage 2, mix input with salt using addition
m = m+s && U32
// Modular stage using Lemire's fast alternative to modulo reduction
return (m * mx) >> 32
end function
function inference(integer cmd, bits, sequence program)
atom out = 0
if length(program) then
for j=0 to bits-1 do
integer {ss, maxx} = program[1],
input = hashtron(cmd||(j<<16), ss, maxx)
for p in program from 2 do
maxx -= p[2]
input = hashtron(input, p[1], maxx)
end for
if odd(input) then
out = or_bitsu(out,1<<j)
end if
end for
end if
return out
end function
constant program = {
{8776,79884}, {12638,1259}, {9953,1242}, {4658,1228}, {5197,1210}, {12043,1201},
{6892,1183}, {7096,1168}, {10924,1149}, {5551,1136}, {5580,1123}, {3735,1107},
{3652,1091}, {12191,1076}, {14214,1062}, {13056,1045}, {14816,1031}, {15205,1017},
{10736,1001}, {9804,989}, {13081,974}, {6706,960}, {13698,944}, {14369,928},
{16806,917}, {9599,906}, {9395,897}, {4885,883}, {10237,870}, {10676,858},
{18518,845}, {2619,833}, {13715,822}, {11065,810}, {9590,799}, {5747,785},
{2627,776}, {8962,764}, {5575,750}, {3448,738}, {5731,725}, {9434,714},
{3163,703}, {3307,690}, {3248,678}, {3259,667}, {3425,657}, {3506,648},
{3270,639}, {3634,627}, {3077,617}, {3511,606}, {27159,597}, {27770,589},
{28496,580}, {28481,571}, {29358,562}, {31027,552}, {30240,543}, {30643,534},
{31351,527}, {31993,519}, {32853,510}, {33078,502}, {33688,495}, {29732,487},
{29898,480}, {29878,474}, {26046,468}, {26549,461}, {28792,453}, {26101,446},
{32971,439}, {29704,432}, {23193,426}, {29509,421}, {27079,415}, {32453,409},
{24737,404}, {25725,400}, {23755,395}, {52538,393}, {53242,386}, {19609,380},
{26492,377}, {24566,358}, {31163,368}, {57174,363}, {26639,364}, {31365,357},
{60918,350}, {21235,338}, {28072,322}, {28811,314}, {27571,320}, {17635,309},
{51968,169}, {54367,323}, {60541,254}, {26732,270}, {52457,157}, {27181,276},
{19874,227}, {22797,320}, {59346,271}, {25496,260}, {54265,231}, {22281,250},
{42977,318}, {26008,240}, {87604,142}, {94647,314}, {52292,157}, {20999,216},
{89253,316}, {22746,29}, {68338,312}, {22557,317}, {110904,104}, {70975,285},
{51835,277}, {51871,313}, {132221,228}, {18522,290}, {68512,285}, {118816,302},
{150865,268}, {68871,273}, {68139,290}, {84984,285}, {150693,266}, {396047,272},
{84923,269}, {215562,258}, {68015,248}, {247689,235}, {214471,229}, {264395,221},
{263287,212}, {280193,201}, {108065,194}, {263616,187}, {148609,176}, {263143,173},
{378205,162}, {312547,154}, {50400,147}, {328927,140}, {279217,132}, {181111,127},
{672098,118}, {657196,113}, {459383,111}, {833281,105}, {520281,102}, {755397,95},
{787994,91}, {492444,82}, {1016592,77}, {656147,71}, {819893,66}, {165531,61},
{886503,57}, {1016551,54}, {3547827,49}, {14398170,43}, {395900,41}, {4950628,37},
{11481175,33}, {100014881,30}, {8955328,31}, {11313984,27}, {13640855,23},
{528553762,21}, {63483027,17}, {952477,8}, {950580,4}, {918378,2}, {918471,1}
}
printf(1,"Test demo:\n")
printf(1,"%d\n\n",inference(42, 64, {{0, 2}}))
sequence res = apply(true,inference,{tagset(255,0),4,{program}})
res = join_by(res,1,16," ",fmt:="%2d")
printf(1,"Square root demo for commands in [0, 255]:\n%s",res)
- Output:
Test demo: 14106184687260844995 Square root demo for commands in [0, 255]: 0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
PHP
// define hashtron hash
$hash = function($n, $s, $max) {
// Ensure the inputs are treated as unsigned 32-bit integers
$n = $n & 0xFFFFFFFF;
$s = $s & 0xFFFFFFFF;
$max = $max & 0xFFFFFFFF;
// Mixing stage, mix input with salt using subtraction
$m = ($n - $s) & 0xFFFFFFFF;
// Hashing stage, use xor shift with prime coefficients
$m ^= ($m << 2) & 0xFFFFFFFF;
$m ^= ($m << 3) & 0xFFFFFFFF;
$m ^= ($m >> 5) & 0xFFFFFFFF;
$m ^= ($m >> 7) & 0xFFFFFFFF;
$m ^= ($m << 11) & 0xFFFFFFFF;
$m ^= ($m << 13) & 0xFFFFFFFF;
$m ^= ($m >> 17) & 0xFFFFFFFF;
$m ^= ($m << 19) & 0xFFFFFFFF;
// Mixing stage 2, mix input with salt using addition
$m = ($m + $s) & 0xFFFFFFFF;
// Modular stage using multiply-shift trick
// Cast to 64-bit integer for multiplication
$result = ((($m & 0xFFFFFFFF) * ($max & 0xFFFFFFFF)) >> 32) & 0xFFFFFFFF;
return $result;
};
// define hashtron inference
$infer = function($command, $bits, $program) {
global $hash;
$out = 0;
$programLength = count($program);
if ($programLength == 0) {
return $out;
}
for ($j = 0; $j < $bits; $j++) {
$input = ($command & 0xFFFFFFFF) | (($j & 0xFF) << 16);
$ss = $program[0][0];
$maxx = $program[0][1];
$input = $hash($input, $ss, $maxx);
for ($i = 1; $i < $programLength; $i++) {
$s = $program[$i][0];
$max = $program[$i][1];
$maxx -= $max;
$input = $hash($input, $s, $maxx);
}
$input &= 1;
if ($input != 0) {
$out |= 1 << $j;
}
}
return $out;
};
Python
def hash(n, s, max_val):
# Mixing stage, mix input with salt using subtraction
m = (n - s) & 0xFFFFFFFF
# Hashing stage, use xor shift with prime coefficients
m ^= (m << 2) & 0xFFFFFFFF
m ^= (m << 3) & 0xFFFFFFFF
m ^= (m >> 5) & 0xFFFFFFFF
m ^= (m >> 7) & 0xFFFFFFFF
m ^= (m << 11) & 0xFFFFFFFF
m ^= (m << 13) & 0xFFFFFFFF
m ^= (m >> 17) & 0xFFFFFFFF
m ^= (m << 19) & 0xFFFFFFFF
# Mixing stage 2, mix input with salt using addition
m += s
m &= 0xFFFFFFFF
# Modular stage using Lemire's fast alternative to modulo reduction
return ((m * max_val) >> 32) & 0xFFFFFFFF
def inference(command, bits, program):
out = 0
# Check if the program is empty
if len(program) == 0:
return out
# Iterate over the bits
for j in range(bits):
input_val = command | (j << 16)
ss, maxx = program[0]
input_val = hash(input_val, ss, maxx)
for i in range(1, len(program)):
s, max_val = program[i]
maxx -= max_val
input_val = hash(input_val, s, maxx)
input_val &= 1
if input_val != 0:
out |= 1 << j
return out
print(inference(42,64,[[0,2]]))
- Output:
14106184687260844995
Raku
# 20240530 Raku programming solution
sub Inference($command, $bits, @program) {
my $out = 0;
return $out unless @program.Bool;
for ^$bits -> $j { # Iterate over the bits
my $input = $command +| ($j +< 16);
$input = Hashtron($input, @program[0][0], my $maxx = @program[0][1]);
for @program[1..*] -> ($s, $max) {
$input = Hashtron($input, $s, $maxx -= $max);
}
if ( $input +&= 1 ) != 0 { $out +|= 1 +< $j }
}
return $out;
}
sub Hashtron($n, $s, $max) {
# Mixing stage, mix input with salt using subtraction
my $m = $n - $s;
# Hashing stage, use xor shift with prime coefficients
for <-2 -3 +5 +7 -11 -13 +17 -19> -> $p {
$m = ($m +^ ($m +> $p)) +& 0xFFFFFFFF;
}
# Mixing stage 2, mix input with salt using addition
$m = ($m + $s) +& 0xFFFFFFFF;
# Modular stage using Lemire's fast alternative to modulo reduction
return (($m * $max) +> 32) +& 0xFFFFFFFF;
}
sub MAIN() {
say Inference(42, 64, (<0 2>,));
for 0..^256 -> $i {
say "$i ", Inference($i, 4, (
<8776 79884>, <12638 1259>, <9953 1242>, <4658 1228>, <5197 1210>,
<12043 1201>, <6892 1183>, <7096 1168>, <10924 1149>, <5551 1136>,
<5580 1123>, <3735 1107>, <3652 1091>, <12191 1076>, <14214 1062>,
<13056 1045>, <14816 1031>, <15205 1017>, <10736 1001>, <9804 989>,
<13081 974>, <6706 960>, <13698 944>, <14369 928>, <16806 917>,
<9599 906>, <9395 897>, <4885 883>, <10237 870>, <10676 858>,
<18518 845>, <2619 833>, <13715 822>, <11065 810>, <9590 799>,
<5747 785>, <2627 776>, <8962 764>, <5575 750>, <3448 738>,
<5731 725>, <9434 714>, <3163 703>, <3307 690>, <3248 678>,
<3259 667>, <3425 657>, <3506 648>, <3270 639>, <3634 627>,
<3077 617>, <3511 606>, <27159 597>, <27770 589>, <28496 580>,
<28481 571>, <29358 562>, <31027 552>, <30240 543>, <30643 534>,
<31351 527>, <31993 519>, <32853 510>, <33078 502>, <33688 495>,
<29732 487>, <29898 480>, <29878 474>, <26046 468>, <26549 461>,
<28792 453>, <26101 446>, <32971 439>, <29704 432>, <23193 426>,
<29509 421>, <27079 415>, <32453 409>, <24737 404>, <25725 400>,
<23755 395>, <52538 393>, <53242 386>, <19609 380>, <26492 377>,
<24566 358>, <31163 368>, <57174 363>, <26639 364>, <31365 357>,
<60918 350>, <21235 338>, <28072 322>, <28811 314>, <27571 320>,
<17635 309>, <51968 169>, <54367 323>, <60541 254>, <26732 270>,
<52457 157>, <27181 276>, <19874 227>, <22797 320>, <59346 271>,
<25496 260>, <54265 231>, <22281 250>, <42977 318>, <26008 240>,
<87604 142>, <94647 314>, <52292 157>, <20999 216>, <89253 316>,
<22746 29>, <68338 312>, <22557 317>, <110904 104>, <70975 285>,
<51835 277>, <51871 313>, <132221 228>, <18522 290>, <68512 285>,
<118816 302>, <150865 268>, <68871 273>, <68139 290>, <84984 285>,
<150693 266>, <396047 272>, <84923 269>, <215562 258>, <68015 248>,
<247689 235>, <214471 229>, <264395 221>, <263287 212>, <280193 201>,
<108065 194>, <263616 187>, <148609 176>, <263143 173>, <378205 162>,
<312547 154>, <50400 147>, <328927 140>, <279217 132>, <181111 127>,
<672098 118>, <657196 113>, <459383 111>, <833281 105>, <520281 102>,
<755397 95>, <787994 91>, <492444 82>, <1016592 77>, <656147 71>,
<819893 66>, <165531 61>, <886503 57>, <1016551 54>, <3547827 49>,
<14398170 43>, <395900 41>, <4950628 37>, <11481175 33>,
<100014881 30>, <8955328 31>, <11313984 27>, <13640855 23>,
<528553762 21>, <63483027 17>, <952477 8>, <950580 4>, <918378 2>,
<918471 1> )
)
}
}
You may Attempt This Online!
- Output:
14106184687260844995 0 0 1 1 2 1 3 1 4 2 5 2 6 2 7 2 8 2 9 3 10 3 11 3 12 3 13 3 14 3 15 3 16 4 17 4 18 4 19 4 20 4 21 4 22 4 23 4 24 4 25 5 26 5 27 5 28 5 29 5 30 5 31 5 32 5 33 5 34 5 35 5 36 6 37 6 38 6 39 6 40 6 41 6 42 6 43 6 44 6 45 6 46 6 47 6 48 6 49 7 50 7 51 7 52 7 53 7 54 7 55 7 56 7 57 7 58 7 59 7 60 7 61 7 62 7 63 7 64 8 65 8 66 8 67 8 68 8 69 8 70 8 71 8 72 8 73 8 74 8 75 8 76 8 77 8 78 8 79 8 80 8 81 9 82 9 83 9 84 9 85 9 86 9 87 9 88 9 89 9 90 9 91 9 92 9 93 9 94 9 95 9 96 9 97 9 98 9 99 9 100 10 101 10 102 10 103 10 104 10 105 10 106 10 107 10 108 10 109 10 110 10 111 10 112 10 113 10 114 10 115 10 116 10 117 10 118 10 119 10 120 10 121 11 122 11 123 11 124 11 125 11 126 11 127 11 128 11 129 11 130 11 131 11 132 11 133 11 134 11 135 11 136 11 137 11 138 11 139 11 140 11 141 11 142 11 143 11 144 12 145 12 146 12 147 12 148 12 149 12 150 12 151 12 152 12 153 12 154 12 155 12 156 12 157 12 158 12 159 12 160 12 161 12 162 12 163 12 164 12 165 12 166 12 167 12 168 12 169 13 170 13 171 13 172 13 173 13 174 13 175 13 176 13 177 13 178 13 179 13 180 13 181 13 182 13 183 13 184 13 185 13 186 13 187 13 188 13 189 13 190 13 191 13 192 13 193 13 194 13 195 13 196 14 197 14 198 14 199 14 200 14 201 14 202 14 203 14 204 14 205 14 206 14 207 14 208 14 209 14 210 14 211 14 212 14 213 14 214 14 215 14 216 14 217 14 218 14 219 14 220 14 221 14 222 14 223 14 224 14 225 15 226 15 227 15 228 15 229 15 230 15 231 15 232 15 233 15 234 15 235 15 236 15 237 15 238 15 239 15 240 15 241 15 242 15 243 15 244 15 245 15 246 15 247 15 248 15 249 15 250 15 251 15 252 15 253 15 254 15 255 15
Wren
import "./long" for ULong
import "./fmt" for Fmt
var hash = Fn.new { |n, s, max|
// 32 bit mask
var k = 0xFFFFFFFF
// Mixing stage, mix input with salt using subtraction
var m = (n - s) & k
// Hashing stage, use xor shift with prime coefficients
m = m ^ ((m << 2) & k)
m = m ^ ((m << 3) & k)
m = m ^ ((m >> 5) & k)
m = m ^ ((m >> 7) & k)
m = m ^ ((m << 11) & k)
m = m ^ ((m << 13) & k)
m = m ^ ((m >> 17) & k)
m = m ^ ((m << 19) & k)
// Mixing stage 2, mix input with salt using addition
m = (m + s) & k
// Modular stage using Lemire's fast alternative to modulo reduction
return ((ULong.new(m) * ULong.new(max)) >> 32).toSmall & k
}
var inference = Fn.new { |command, bits, program|
var out = ULong.zero
// Check if the program is empty
if (program.count == 0) return out
// Iterate over the bits
for (j in 0...bits) {
var input = command | (j << 16)
var ss = program[0][0]
var maxx = program [0][1]
input = hash.call(input, ss, maxx)
for (i in 1...program.count) {
var s = program[i][0]
var max = program[i][1]
maxx = maxx - max
input = hash.call(input, s, maxx)
}
input = input & 1
if (input != 0) out = out | (ULong.one << j)
}
return out
}
System.print("Test demo:")
var program = [[0, 2]]
System.print(inference.call(42, 64, program))
program = [
[8776,79884], [12638,1259], [9953,1242], [4658,1228], [5197,1210], [12043,1201],
[6892,1183], [7096,1168], [10924,1149], [5551,1136], [5580,1123], [3735,1107],
[3652,1091], [12191,1076], [14214,1062], [13056,1045], [14816,1031], [15205,1017],
[10736,1001], [9804,989], [13081,974], [6706,960], [13698,944], [14369,928],
[16806,917], [9599,906], [9395,897], [4885,883], [10237,870], [10676,858],
[18518,845], [2619,833], [13715,822], [11065,810], [9590,799], [5747,785],
[2627,776], [8962,764], [5575,750], [3448,738], [5731,725], [9434,714],
[3163,703], [3307,690], [3248,678], [3259,667], [3425,657], [3506,648],
[3270,639], [3634,627], [3077,617], [3511,606], [27159,597], [27770,589],
[28496,580], [28481,571], [29358,562], [31027,552], [30240,543], [30643,534],
[31351,527], [31993,519], [32853,510], [33078,502], [33688,495], [29732,487],
[29898,480], [29878,474], [26046,468], [26549,461], [28792,453], [26101,446],
[32971,439], [29704,432], [23193,426], [29509,421], [27079,415], [32453,409],
[24737,404], [25725,400], [23755,395], [52538,393], [53242,386], [19609,380],
[26492,377], [24566,358], [31163,368], [57174,363], [26639,364], [31365,357],
[60918,350], [21235,338], [28072,322], [28811,314], [27571,320], [17635,309],
[51968,169], [54367,323], [60541,254], [26732,270], [52457,157], [27181,276],
[19874,227], [22797,320], [59346,271], [25496,260], [54265,231], [22281,250],
[42977,318], [26008,240], [87604,142], [94647,314], [52292,157], [20999,216],
[89253,316], [22746,29], [68338,312], [22557,317], [110904,104], [70975,285],
[51835,277], [51871,313], [132221,228], [18522,290], [68512,285], [118816,302],
[150865,268], [68871,273], [68139,290], [84984,285], [150693,266], [396047,272],
[84923,269], [215562,258], [68015,248], [247689,235], [214471,229], [264395,221],
[263287,212], [280193,201], [108065,194], [263616,187], [148609,176], [263143,173],
[378205,162], [312547,154], [50400,147], [328927,140], [279217,132], [181111,127],
[672098,118], [657196,113], [459383,111], [833281,105], [520281,102], [755397,95],
[787994,91], [492444,82], [1016592,77], [656147,71], [819893,66], [165531,61],
[886503,57], [1016551,54], [3547827,49], [14398170,43], [395900,41], [4950628,37],
[11481175,33], [100014881,30], [8955328,31], [11313984,27], [13640855,23],
[528553762,21], [63483027,17], [952477,8], [950580,4], [918378,2], [918471,1]
]
System.print("\nSquare root demo for commands in [0, 255]:")
Fmt.tprint("$2i", (0..255).map { |i| inference.call(i, 4, program) }, 16)
- Output:
Test demo: 14106184687260844995 Square root demo for commands in [0, 255]: 0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15