math.c

#include "math.h"

const
unsigned char
math::clz_lut[256] =
{
	8,7,6,6,5,5,5,5,4,4,4,4,4,4,4,4,
	3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,
	2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
	2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
};

const
unsigned int
math::rcp_lut[RCP_LUT_SIZE] =
{
	0x80000000,0x7fe007fe,0x7fc01ff0,0x7fa047ca,
	0x7f807f80,0x7f60c707,0x7f411e52,0x7f218556,
	0x7f01fc07,0x7ee2825a,0x7ec31843,0x7ea3bdb6,
	0x7e8472a8,0x7e65370d,0x7e460ada,0x7e26ee03,
	0x7e07e07e,0x7de8e23e,0x7dc9f339,0x7dab1363,
	0x7d8c42b2,0x7d6d811a,0x7d4ece8f,0x7d302b08,
	0x7d119679,0x7cf310d6,0x7cd49a16,0x7cb6322d,
	0x7c97d910,0x7c798eb5,0x7c5b5311,0x7c3d2618,
	0x7c1f07c1,0x7c00f801,0x7be2f6ce,0x7bc5041c,
	0x7ba71fe1,0x7b894a12,0x7b6b82a6,0x7b4dc992,
	0x7b301ecc,0x7b128248,0x7af4f3fe,0x7ad773e2,
	0x7aba01ea,0x7a9c9e0d,0x7a7f4841,0x7a62007a,
	0x7a44c6af,0x7a279ad7,0x7a0a7ce6,0x79ed6cd4,
	0x79d06a96,0x79b37622,0x79968f6f,0x7979b673,
	0x795ceb24,0x79402d78,0x79237d65,0x7906dae3,
	0x78ea45e7,0x78cdbe68,0x78b1445c,0x7894d7ba,
	0x78787878,0x785c268d,0x783fe1f0,0x7823aa96,
	0x78078078,0x77eb638a,0x77cf53c5,0x77b35120,
	0x77975b8f,0x777b730c,0x775f978c,0x7743c906,
	0x77280772,0x770c52c6,0x76f0aaf9,0x76d51003,
	0x76b981da,0x769e0076,0x76828bce,0x766723d8,
	0x764bc88c,0x763079e1,0x761537d0,0x75fa024d,
	0x75ded952,0x75c3bcd6,0x75a8accf,0x758da936,
	0x7572b201,0x7557c729,0x753ce8a4,0x7522166b,
	0x75075075,0x74ec96b8,0x74d1e92f,0x74b747ce,
	0x749cb28f,0x7482296a,0x7467ac55,0x744d3b49,
	0x7432d63d,0x74187d2a,0x73fe3007,0x73e3eecc,
	0x73c9b971,0x73af8fed,0x7395723a,0x737b604f,
	0x73615a24,0x73475fb0,0x732d70ed,0x73138dd2,
	0x72f9b658,0x72dfea76,0x72c62a24,0x72ac755c,
	0x7292cc15,0x72792e47,0x725f9bec,0x724614fa,
	0x722c996b,0x72132937,0x71f9c457,0x71e06ac2,
	0x71c71c71,0x71add95d,0x7194a17f,0x717b74ce,
	0x71625344,0x71493cd8,0x71303185,0x71173141,
	0x70fe3c07,0x70e551ce,0x70cc728f,0x70b39e44,
	0x709ad4e4,0x70821669,0x706962cc,0x7050ba05,
	0x70381c0e,0x701f88de,0x70070070,0x6fee82bb,
	0x6fd60fba,0x6fbda764,0x6fa549b4,0x6f8cf6a1,
	0x6f74ae26,0x6f5c703b,0x6f443cd9,0x6f2c13f9,
	0x6f13f596,0x6efbe1a7,0x6ee3d826,0x6ecbd90c,
	0x6eb3e453,0x6e9bf9f3,0x6e8419e6,0x6e6c4426,
	0x6e5478ac,0x6e3cb771,0x6e25006e,0x6e0d539d,
	0x6df5b0f7,0x6dde1876,0x6dc68a13,0x6daf05c8,
	0x6d978b8e,0x6d801b60,0x6d68b535,0x6d515908,
	0x6d3a06d3,0x6d22be8f,0x6d0b8036,0x6cf44bc1,
	0x6cdd212b,0x6cc6006c,0x6caee97f,0x6c97dc5e,
	0x6c80d901,0x6c69df64,0x6c52ef7f,0x6c3c094d,
	0x6c252cc7,0x6c0e59e7,0x6bf790a8,0x6be0d103,
	0x6bca1af2,0x6bb36e6f,0x6b9ccb74,0x6b8631fb,
	0x6b6fa1fe,0x6b591b77,0x6b429e60,0x6b2c2ab3,
	0x6b15c06b,0x6aff5f80,0x6ae907ef,0x6ad2b9b0,
	0x6abc74be,0x6aa63912,0x6a9006a9,0x6a79dd7a,
	0x6a63bd81,0x6a4da6b8,0x6a37991a,0x6a2194a0,
	0x6a0b9944,0x69f5a702,0x69dfbdd4,0x69c9ddb3,
	0x69b4069b,0x699e3885,0x6988736d,0x6972b74c,
	0x695d041d,0x694759db,0x6931b880,0x691c2006,
	0x69069069,0x68f109a2,0x68db8bac,0x68c61682,
	0x68b0aa1f,0x689b467c,0x6885eb95,0x68709965,
	0x685b4fe5,0x68460f12,0x6830d6e4,0x681ba758,
	0x68068068,0x67f1620e,0x67dc4c45,0x67c73f09,
	0x67b23a54,0x679d3e20,0x67884a69,0x67735f2a,
	0x675e7c5d,0x6749a1fd,0x6734d006,0x67200672,
	0x670b453b,0x66f68c5e,0x66e1dbd4,0x66cd339a,
	0x66b893a9,0x66a3fbfd,0x668f6c91,0x667ae561,
	0x66666666,0x6651ef9c,0x663d80ff,0x66291a89,
	0x6614bc36,0x66006600,0x65ec17e3,0x65d7d1da,
	0x65c393e0,0x65af5df0,0x659b3006,0x65870a1c,
	0x6572ec2f,0x655ed639,0x654ac835,0x6536c220,
	0x6522c3f3,0x650ecdab,0x64fadf42,0x64e6f8b5,
	0x64d319fe,0x64bf4319,0x64ab7401,0x6497acb2,
	0x6483ed27,0x6470355b,0x645c854a,0x6448dcf0,
	0x64353c48,0x6421a34c,0x640e11fa,0x63fa884c,
	0x63e7063e,0x63d38bcb,0x63c018f0,0x63acada6,
	0x639949eb,0x6385edba,0x6372990e,0x635f4be3,
	0x634c0634,0x6338c7fe,0x6325913c,0x631261e9,
	0x62ff3a01,0x62ec1980,0x62d90062,0x62c5eea3,
	0x62b2e43d,0x629fe12e,0x628ce570,0x6279f0ff,
	0x626703d8,0x62541df5,0x62413f54,0x622e67ef,
	0x621b97c2,0x6208ceca,0x61f60d02,0x61e35266,
	0x61d09ef3,0x61bdf2a3,0x61ab4d72,0x6198af5e,
	0x61861861,0x61738878,0x6160ff9e,0x614e7dd0,
	0x613c0309,0x61298f46,0x61172283,0x6104bcbb,
	0x60f25dea,0x60e0060e,0x60cdb520,0x60bb6b1f,
	0x60a92806,0x6096ebd0,0x6084b67a,0x60728801,
	0x60606060,0x604e3f93,0x603c2597,0x602a1268,
	0x60180601,0x60060060,0x5ff4017f,0x5fe2095d,
	0x5fd017f4,0x5fbe2d40,0x5fac493f,0x5f9a6bed,
	0x5f889545,0x5f76c544,0x5f64fbe6,0x5f533928,
	0x5f417d05,0x5f2fc77b,0x5f1e1885,0x5f0c7020,
	0x5eface48,0x5ee932fa,0x5ed79e31,0x5ec60feb,
	0x5eb48823,0x5ea306d6,0x5e918c01,0x5e8017a0,
	0x5e6ea9ae,0x5e5d422a,0x5e4be10f,0x5e3a8659,
	0x5e293205,0x5e17e410,0x5e069c77,0x5df55b34,
	0x5de42046,0x5dd2eba8,0x5dc1bd58,0x5db09551,
	0x5d9f7390,0x5d8e5813,0x5d7d42d4,0x5d6c33d2,
	0x5d5b2b08,0x5d4a2873,0x5d392c10,0x5d2835db,
	0x5d1745d1,0x5d065bef,0x5cf57831,0x5ce49a94,
	0x5cd3c315,0x5cc2f1af,0x5cb22661,0x5ca16127,
	0x5c90a1fd,0x5c7fe8e0,0x5c6f35cc,0x5c5e88bf,
	0x5c4de1b6,0x5c3d40ac,0x5c2ca5a0,0x5c1c108d,
	0x5c0b8170,0x5bfaf846,0x5bea750c,0x5bd9f7bf,
	0x5bc9805b,0x5bb90ede,0x5ba8a344,0x5b983d8a,
	0x5b87ddad,0x5b7783a9,0x5b672f7c,0x5b56e123,
	0x5b46989a,0x5b3655de,0x5b2618ec,0x5b15e1c1,
	0x5b05b05b,0x5af584b5,0x5ae55ecd,0x5ad53ea0,
	0x5ac5242a,0x5ab50f69,0x5aa5005a,0x5a94f6fa,
	0x5a84f345,0x5a74f539,0x5a64fcd2,0x5a550a0e,
	0x5a451cea,0x5a353562,0x5a255374,0x5a15771d,
	0x5a05a05a,0x59f5cf27,0x59e60382,0x59d63d69,
	0x59c67cd8,0x59b6c1cb,0x59a70c41,0x59975c37,
	0x5987b1a9,0x59780c94,0x59686cf7,0x5958d2cd,
	0x59493e14,0x5939aeca,0x592a24eb,0x591aa074,
	0x590b2164,0x58fba7b6,0x58ec3368,0x58dcc478,
	0x58cd5ae2,0x58bdf6a3,0x58ae97ba,0x589f3e23,
	0x588fe9dc,0x58809ae1,0x58715130,0x58620cc6,
	0x5852cda0,0x584393bd,0x58345f18,0x58252fb0,
	0x58160581,0x5806e089,0x57f7c0c5,0x57e8a633,
	0x57d990d0,0x57ca8099,0x57bb758c,0x57ac6fa5,
	0x579d6ee3,0x578e7342,0x577f7cc0,0x57708b5b,
	0x57619f0f,0x5752b7db,0x5743d5bb,0x5734f8ad,
	0x572620ae,0x57174dbc,0x57087fd4,0x56f9b6f4,
	0x56eaf319,0x56dc3440,0x56cd7a67,0x56bec58c,
	0x56b015ac,0x56a16ac3,0x5692c4d1,0x568423d2,
	0x567587c4,0x5666f0a4,0x56585e70,0x5649d125,
	0x563b48c2,0x562cc542,0x561e46a4,0x560fcce6,
	0x56015805,0x55f2e7fe,0x55e47cd0,0x55d61677,
	0x55c7b4f1,0x55b9583c,0x55ab0055,0x559cad3b,
	0x558e5ee9,0x55801560,0x5571d09a,0x55639098,
	0x55555555,0x55471ed0,0x5538ed06,0x552abff5,
	0x551c979a,0x550e73f4,0x55005500,0x54f23abb,
	0x54e42523,0x54d61437,0x54c807f2,0x54ba0054,
	0x54abfd5a,0x549dff02,0x54900549,0x5482102c,
	0x54741fab,0x546633c2,0x54584c70,0x544a69b1,
	0x543c8b84,0x542eb1e6,0x5420dcd6,0x54130c50,
	0x54054054,0x53f778dd,0x53e9b5eb,0x53dbf77b,
	0x53ce3d8b,0x53c08818,0x53b2d721,0x53a52aa3,
	0x5397829c,0x5389df0a,0x537c3feb,0x536ea53c,
	0x53610efb,0x53537d26,0x5345efbc,0x533866b9,
	0x532ae21c,0x531d61e3,0x530fe60b,0x53026e92,
	0x52f4fb76,0x52e78cb6,0x52da224e,0x52ccbc3d,
	0x52bf5a81,0x52b1fd17,0x52a4a3fe,0x52974f34,
	0x5289feb5,0x527cb281,0x526f6a96,0x526226f0,
	0x5254e78e,0x5247ac6f,0x523a758f,0x522d42ed,
	0x52201488,0x5212ea5c,0x5205c467,0x51f8a2a9,
	0x51eb851e,0x51de6bc5,0x51d1569c,0x51c445a1,
	0x51b738d1,0x51aa302b,0x519d2bad,0x51902b54,
	0x51832f1f,0x5176370c,0x51694319,0x515c5344,
	0x514f678b,0x51427feb,0x51359c64,0x5128bcf2,
	0x511be195,0x510f0a4a,0x5102370f,0x50f567e2,
	0x50e89cc2,0x50dbd5ac,0x50cf129f,0x50c25399,
	0x50b59897,0x50a8e198,0x509c2e9a,0x508f7f9b,
	0x5082d499,0x50762d92,0x50698a85,0x505ceb70,
	0x50505050,0x5043b924,0x503725ea,0x502a96a0,
	0x501e0b44,0x501183d4,0x50050050,0x4ff880b3,
	0x4fec04fe,0x4fdf8d2e,0x4fd31941,0x4fc6a936,
	0x4fba3d0a,0x4fadd4bc,0x4fa1704a,0x4f950fb2,
	0x4f88b2f3,0x4f7c5a0a,0x4f7004f7,0x4f63b3b6,
	0x4f576646,0x4f4b1ca6,0x4f3ed6d4,0x4f3294ce,
	0x4f265691,0x4f1a1c1e,0x4f0de571,0x4f01b289,
	0x4ef58364,0x4ee95801,0x4edd305d,0x4ed10c78,
	0x4ec4ec4e,0x4eb8cfe0,0x4eacb72a,0x4ea0a22b,
	0x4e9490e1,0x4e88834c,0x4e7c7968,0x4e707335,
	0x4e6470b0,0x4e5871d8,0x4e4c76ab,0x4e407f28,
	0x4e348b4d,0x4e289b18,0x4e1cae88,0x4e10c59a,
	0x4e04e04e,0x4df8fea1,0x4ded2092,0x4de1461f,
	0x4dd56f47,0x4dc99c07,0x4dbdcc5f,0x4db2004d,
	0x4da637cf,0x4d9a72e3,0x4d8eb188,0x4d82f3bc,
	0x4d77397e,0x4d6b82cc,0x4d5fcfa4,0x4d542004,
	0x4d4873ec,0x4d3ccb5a,0x4d31264b,0x4d2584bf,
	0x4d19e6b3,0x4d0e4c27,0x4d02b518,0x4cf72185,
	0x4ceb916d,0x4ce004ce,0x4cd47ba5,0x4cc8f5f3,
	0x4cbd73b5,0x4cb1f4ea,0x4ca67990,0x4c9b01a5,
	0x4c8f8d28,0x4c841c18,0x4c78ae73,0x4c6d4437,
	0x4c61dd63,0x4c5679f6,0x4c4b19ed,0x4c3fbd48,
	0x4c346404,0x4c290e21,0x4c1dbb9d,0x4c126c76,
	0x4c0720ab,0x4bfbd83a,0x4bf09322,0x4be55161,
	0x4bda12f6,0x4bced7e0,0x4bc3a01c,0x4bb86baa,
	0x4bad3a87,0x4ba20cb4,0x4b96e22d,0x4b8bbaf2,
	0x4b809701,0x4b757658,0x4b6a58f7,0x4b5f3edb,
	0x4b542804,0x4b491470,0x4b3e041d,0x4b32f70a,
	0x4b27ed36,0x4b1ce69e,0x4b11e343,0x4b06e321,
	0x4afbe639,0x4af0ec88,0x4ae5f60d,0x4adb02c7,
	0x4ad012b4,0x4ac525d2,0x4aba3c21,0x4aaf55a0,
	0x4aa4724b,0x4a999223,0x4a8eb526,0x4a83db53,
	0x4a7904a7,0x4a6e3122,0x4a6360c3,0x4a589387,
	0x4a4dc96e,0x4a430277,0x4a383e9f,0x4a2d7de6,
	0x4a22c04a,0x4a1805c9,0x4a0d4e64,0x4a029a17,
	0x49f7e8e2,0x49ed3ac4,0x49e28fba,0x49d7e7c5,
	0x49cd42e2,0x49c2a10f,0x49b8024d,0x49ad6699,
	0x49a2cdf3,0x49983858,0x498da5c8,0x49831641,
	0x497889c2,0x496e0049,0x496379d6,0x4958f666,
	0x494e75fa,0x4943f88f,0x49397e24,0x492f06b7,
	0x49249249,0x491a20d6,0x490fb25f,0x490546e1,
	0x48fade5c,0x48f078ce,0x48e61636,0x48dbb692,
	0x48d159e2,0x48c70024,0x48bca957,0x48b25579,
	0x48a8048a,0x489db688,0x48936b72,0x48892346,
	0x487ede04,0x48749baa,0x486a5c37,0x48601faa,
	0x4855e601,0x484baf3b,0x48417b57,0x48374a54,
	0x482d1c31,0x4822f0ec,0x4818c884,0x480ea2f9,
	0x48048048,0x47fa6070,0x47f04371,0x47e62949,
	0x47dc11f7,0x47d1fd79,0x47c7ebcf,0x47bddcf8,
	0x47b3d0f1,0x47a9c7bb,0x479fc154,0x4795bdba,
	0x478bbcec,0x4781beea,0x4777c3b2,0x476dcb43,
	0x4763d59c,0x4759e2bc,0x474ff2a1,0x4746054a,
	0x473c1ab6,0x473232e4,0x47284dd4,0x471e6b82,
	0x47148bf0,0x470aaf1b,0x4700d502,0x46f6fda4,
	0x46ed2901,0x46e35716,0x46d987e3,0x46cfbb66,
	0x46c5f19f,0x46bc2a8d,0x46b2662d,0x46a8a480,
	0x469ee584,0x46952938,0x468b6f9a,0x4681b8aa,
	0x46780467,0x466e52cf,0x4664a3e2,0x465af79e,
	0x46514e02,0x4647a70d,0x463e02be,0x46346114,
	0x462ac20e,0x462125aa,0x46178be9,0x460df4c7,
	0x46046046,0x45face62,0x45f13f1c,0x45e7b272,
	0x45de2864,0x45d4a0f0,0x45cb1c14,0x45c199d1,
	0x45b81a25,0x45ae9d0e,0x45a5228c,0x459baa9f,
	0x45923543,0x4588c27a,0x457f5241,0x4575e498,
	0x456c797d,0x456310f0,0x4559aaf0,0x4550477a,
	0x4546e68f,0x453d882e,0x45342c55,0x452ad303,
	0x45217c38,0x451827f1,0x450ed630,0x450586f1,
	0x44fc3a34,0x44f2eff9,0x44e9a83e,0x44e06302,
	0x44d72044,0x44cde004,0x44c4a23f,0x44bb66f6,
	0x44b22e27,0x44a8f7d1,0x449fc3f4,0x4496928d,
	0x448d639d,0x44843722,0x447b0d1b,0x4471e587,
	0x4468c066,0x445f9db6,0x44567d76,0x444d5fa6,
	0x44444444,0x443b2b4f,0x443214c7,0x442900aa,
	0x441feef8,0x4416dfaf,0x440dd2ce,0x4404c856,
	0x43fbc043,0x43f2ba97,0x43e9b74f,0x43e0b66b,
	0x43d7b7ea,0x43cebbcb,0x43c5c20d,0x43bccaae,
	0x43b3d5af,0x43aae30e,0x43a1f2ca,0x439904e2,
	0x43901956,0x43873023,0x437e494b,0x437564ca,
	0x436c82a2,0x4363a2d0,0x435ac553,0x4351ea2c,
	0x43491158,0x43403ad8,0x433766a9,0x432e94cc,
	0x4325c53e,0x431cf801,0x43142d11,0x430b646f,
	0x43029e1a,0x42f9da10,0x42f11851,0x42e858dc,
	0x42df9bb0,0x42d6e0cc,0x42ce2830,0x42c571d9,
	0x42bcbdc8,0x42b40bfc,0x42ab5c73,0x42a2af2d,
	0x429a0429,0x42915b66,0x4288b4e3,0x428010a0,
	0x42776e9a,0x426eced2,0x42663147,0x425d95f8,
	0x4254fce4,0x424c6609,0x4243d168,0x423b3eff,
	0x4232aecd,0x422a20d2,0x4221950d,0x42190b7d,
	0x42108421,0x4207fef7,0x41ff7c01,0x41f6fb3b,
	0x41ee7ca6,0x41e60041,0x41dd860b,0x41d50e03,
	0x41cc9829,0x41c4247a,0x41bbb2f8,0x41b343a0,
	0x41aad671,0x41a26b6c,0x419a0290,0x41919bda,
	0x4189374b,0x4180d4e2,0x4178749e,0x4170167e,
	0x4167ba81,0x415f60a7,0x415708ee,0x414eb357,
	0x41465fdf,0x413e0e86,0x4135bf4c,0x412d7230,
	0x41252730,0x411cde4c,0x41149783,0x410c52d5,
	0x41041041,0x40fbcfc5,0x40f39161,0x40eb5514,
	0x40e31ade,0x40dae2bd,0x40d2acb1,0x40ca78b9,
	0x40c246d4,0x40ba1702,0x40b1e941,0x40a9bd91,
	0x40a193f1,0x40996c61,0x409146df,0x4089236b,
	0x40810204,0x4078e2a8,0x4070c559,0x4068aa14,
	0x406090d9,0x405879a7,0x4050647d,0x4048515b,
	0x40404040,0x4038312b,0x4030241b,0x4028190f,
	0x40201008,0x40180903,0x40100401,0x40080100
};

math.h

#ifndef MATH_H
#define MATH_H

namespace math
{
	extern const
	unsigned char
	clz_lut[256];

	inline
	unsigned int
	clz(unsigned int n)
	{
		unsigned int ret = 0;

		if (n < (1 << 16)) ret += 16;
		else n >>= 16;

		if (n < (1 << 8)) ret += 8;
		else n >>= 8;

		ret += clz_lut[n];
		return ret;
	}

#define RCP_LUT_LOG2_SIZE 10
#define RCP_LUT_SIZE (1 << (RCP_LUT_LOG2_SIZE))

	extern const
	unsigned int
	rcp_lut[RCP_LUT_SIZE];
	
	// 16:16 fixed point 1.0 / n
	inline
	unsigned int
	urcp(unsigned int n)
	{
		// 1.0 / 0 is undefined, we'll use the highest possible value
		if (0 == n) return 0xFFFFFFFF;

		// normalize number
		unsigned int shift = clz(n);
		n <<= shift + 1; // shift away the top-bit. We know it's there anyway

		// look up, and scale back to the right range
		unsigned int result = rcp_lut[n >> (32 - (RCP_LUT_LOG2_SIZE))];
		return result >> (30 - shift);
	}

	inline
	int
	rcp(int n)
	{
		// take the absolute value
		bool neg = n < 0;
		if (neg) n = -n;

		int result = int(urcp(n));

		// flip result back
		if (neg) result = -result;
		return result;
	}
}

#endif // defined(MATH_H)

rcp.py

import math


clz_lut_log2_size = 8
clz_lut_size = 1 << clz_lut_log2_size

def clz_lut_func(n):
    if 0 == n: return clz_lut_log2_size
    for i in range(clz_lut_log2_size):
        if ((1 << (clz_lut_log2_size - 1 - i)) & n) != 0: return i
#    if 0 == n: return 8
#    return 8 - int(math.log(float(n)) / math.log(2.0))

clz_lut = [clz_lut_func(n) for n in range(clz_lut_size)]

def clz(n):
    ret = 0

    # first iteration of binary search
    if n < (1 << 16): ret += 16
    else: n >>= 16
    
    if n < (1 << 8):  ret += 8
    else: n >>= 8
    
    ret += clz_lut[n]
    return ret;

rcp_lut_log2_size = 10
rcp_lut_size = 1 << rcp_lut_log2_size

def rcp_lut_func(n):
    if 0 == n: return 1
    return 1.0 / (1 + float(n) / rcp_lut_size)

rcp_lut = [int(rcp_lut_func(n) * (1 << 31)) for n in range(rcp_lut_size)]

def rcp(f):
    n = int(f * 65536)
    if 0 == n: return 0

    shift = clz(n)
    n <<= shift + 1
    n &= 0xFFFFFFFF

    return rcp_lut[n >> (32 - rcp_lut_log2_size)] >> (30 - shift);

# print rcp_lut

print int(65536 / 1.0)
print rcp(1.0)

print int(65536 / 0.5)
print rcp(0.5)

print int(65536 / 0.25)
print rcp(0.25)

print int(65536 / 0.75)
print rcp(0.75)

print int(65536 / 0.499)
print rcp(0.499)

print int(65536 / 0.501)
print rcp(0.501)

print int(65536 / 0.33)
print rcp(0.33)

import sys
i = 0
# for n in rcp_lut:
#    sys.stdout.write('0x%x, ' % n)
#    if (i % 4) == 3: sys.stdout.write('\n\t')
#    i += 1
#    print hex(n)