UVA: 100 Programming Challenges (Skiena & Revilla) Volume-1

UVA 100 3n+1

Background- This is classical unsolved problem, for more on problem description, visit UVA 100 3n+1.  I tried this problem with my best effort and time to solve but unfortunately couldn't match the best timing. It has been learnt that there are implementations which have solved the this problem in just no time i.e. 0.000. Though I could manage to get my best timing of 0.020 sec with rank 830. If you got better approach and/or you want  to share short comings on the below implementation, please do post your ideas. My implementation is as follows -  

Algorithm: 
 * HSS_CYCLE_LEN len, num
 * a. len := no. of trailing zeros // n/2
 * b. num >>= len 
 * c. key :- hash_key(num)

 // num in chache no need to compute

 * d. if key < chache_size && chache[key] != 0 
 * retuurn len+chache[key]

 // num in not chache compute and update chache

 * e. else if(key < chache_size && chache[key] == 0 
 * chache[key] = 1 + HSS_CYCLE_LEN(num >> 1 + num +1) // 3n+1
 * return len + chache[key]
 * f. else
 * return 1 + len + HSS_CYCLE_LEN(num >> 1 + num +1) 

Following optimizations have been made to improve time complexity-

•  Only odd elements are being chached or hashed 
•  Pre-computed chache of first 2048 odd elements is being used.
• Dynamic, direct on the fly hash O(1) operation
• Bit-wise mathematical operations are used as much as possible 
• Tried my level best not to branch the execution
• Elements having cycle length 325 or greater are chached and if the range A-B includes the elements of that chache max length will be returned by just look-up and binary search log(n) operation

C Implementation - 

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
using namespace std;
#define ultype unsigned long 
#define ltype long
#define CHAR_BIT 8
ultype  Max(ultype x, ultype y) {
    return x ^ ((x ^ y) & -(x < y));
}
ultype  Min(ultype x, ultype y) {
    return y ^ ((x ^ y) & -(x < y));
}
ltype Abs(ltype v) {
    ltype mask = v >> ((sizeof(ltype) * CHAR_BIT) - 1);
    return (v + mask) ^ mask;
}
static unsigned long Mod37BitPosition[]={32,0,1,26,2,23,27,0,3,16,24,30,28,11,0,13,4,7,17,0,25,22,31,15,29,10,12,6,0,21,14,9,5,20,8,19,18};
#define pre_guess_size  2411
static short pre_len[pre_guess_size]=\
{340,335,330,325,325,325,325,351,338,333,\
333,333,328,328,328,341,341,341,354,349,\
336,336,336,336,331,331,331,331,331,344,\
331,331,331,344,331,344,326,326,375,326,\
326,326,326,357,326,326,326,326,326,370,\
339,352,352,326,383,339,339,352,370,339,\
334,352,352,334,334,334,334,334,334,347,\
334,334,334,334,334,334,347,365,334,334,\
329,347,329,329,360,329,329,329,329,329,\
329,329,347,342,329,329,342,360,329,329,\
329,329,329,329,329,342,342,342,342,355,\
329,342,373,342,342,342,355,355,355,373,\
386,342,337,355,355,337,368,337,368,337,\
337,355,443,350,350,337,368,381,337,337,\
337,337,337,350,350,368,337,337,337,332,\
332,332,350,350,350,350,332,332,332,332,\
332,363,332,332,332,332,345,332,332,345,\
345,332,332,332,407,332,332,332,332,332,\
332,345,345,345,345,345,407,363,345,358,\
332,332,345,389,327,345,345,345,345,327,\
327,327,358,327,358,327,327,358,376,376,\
327,327,327,327,327,327,327,327,389,327,\
327,327,389,345,340,327,327,327,340,358,\
358,327,358,358,327,327,327,327,371,327,\
327,327,327,327,327,371,371,340,340,340,\
327,340,340,371,353,353,353,327,327,340,\
340,371,371,384,384,353,340,340,340,340,\
340,353,353,353,353,371,371,353,384,340,\
340,340,335,335,353,353,353,353,353,353,\
353,335,335,335,335,366,366,335,335,335,\
366,335,335,335,335,335,335,335,335,353,\
335,335,441,348,348,335,335,335,366,335,\
379,348,335,335,335,335,348,335,335,335,\
335,335,379,379,348,348,379,348,348,348,\
348,348,410,366,366,348,361,361,335,335,\
335,330,348,348,361,392,392,330,330,348,\
348,348,348,348,348,330,330,330,330,361,\
330,330,423,330,330,361,330,361,361,361,\
379,330,330,330,330,330,374,361,330,330,\
330,330,330,330,330,330,330,330,330,348,\
348,343,343,330,330,330,330,330,436,361,\
343,343,361,361,330,330,330,361,361,343,\
405,330,330,330,330,330,343,374,330,330,\
330,330,330,330,330,374,343,343,343,343,\
387,343,330,343,343,343,343,405,343,343,\
361,343,343,449,374,356,356,356,330,330,\
343,343,343,343,374,374,374,343,387,387,\
325,343,343,343,343,343,343,343,343,343,\
325,325,325,325,356,356,325,325,418,356,\
356,356,325,325,356,356,356,356,356,374,\
374,325,325,325,325,325,325,325,343,325,\
325,325,387,387,369,325,325,325,325,325,\
387,325,325,343,343,343,338,338,325,325,\
356,325,325,325,325,387,325,400,338,338,\
325,356,356,325,325,325,325,356,356,356,\
325,325,338,338,338,325,325,325,338,338,\
325,325,325,325,325,325,369,338,325,325,\
325,325,325,325,325,325,325,369,369,369,\
369,387,338,338,338,369,369,338,338,325,\
338,338,338,338,338,338,338,338,356,356,\
351,338,444,444,369,351,351,351,325,325,\
325,338,338,338,338,338,369,369,369,369,\
413,382,382,351,338,338,338,338,338,338,\
338,338,338,338,338,382,351,351,382,351,\
351,351,338,351,351,351,351,413,351,369,\
369,351,382,351,338,382,364,382,338,338,\
338,338,333,333,382,351,426,395,333,333,\
333,351,351,351,351,351,351,351,351,351,\
351,333,333,333,395,364,333,333,333,333,\
426,333,333,364,364,364,364,382,382,333,\
333,333,333,333,333,364,333,377,364,364,\
333,470,333,333,333,333,333,333,333,333,\
333,333,333,351,351,346,346,364,333,333,\
333,395,333,333,439,364,346,346,346,333,\
364,333,333,333,333,333,364,364,408,346,\
408,408,333,377,333,346,333,333,333,377,\
333,333,333,346,346,333,333,333,333,333,\
333,333,333,377,377,346,346,346,333,377,\
346,346,346,333,346,346,346,346,346,346,\
346,408,408,364,364,346,346,346,359,346,\
452,377,359,359,359,333,333,333,328,346,\
346,346,377,346,421,359,346,390,390,390,\
328,328,359,346,346,346,346,346,346,346,\
359,346,346,346,346,328,328,328,328,328,\
328,359,359,328,328,328,328,421,328,328,\
359,359,359,359,328,328,328,359,346,346,\
359,359,359,359,359,359,377,377,377,328,\
328,328,328,328,359,372,359,328,328,328,\
328,328,328,328,328,346,328,328,328,328,\
328,328,390,390,372,328,328,328,328,328,\
328,390,390,328,346,346,346,341,341,359,\
328,328,328,328,328,328,328,328,328,328,\
328,328,434,372,359,341,341,341,359,328,\
359,359,359,328,328,328,328,328,328,359,\
359,359,359,359,328,328,359,328,341,341,\
341,403,328,328,328,328,328,328,328,328,\
328,372,328,328,341,372,372,341,328,328,\
328,328,328,328,328,328,328,328,328,328,\
372,372,372,372,372,341,341,341,341,341,\
403,385,372,372,341,341,328,328,328,341,\
341,341,341,341,341,341,341,403,341,341,\
341,359,359,341,341,341,341,354,447,372,\
372,354,354,354,354,328,328,328,372,341,\
341,341,341,341,341,372,372,372,372,354,\
341,341,385,385,385,385,385,341,341,354,\
354,341,341,341,341,509,341,341,341,341,\
341,341,341,341,341,385,328,354,354,354,\
416,354,354,354,354,354,341,354,354,354,\
354,354,354,354,416,354,354,372,372,372,\
354,354,416,354,354,341,385,385,385,354,\
367,385,341,341,341,341,341,336,336,354,\
354,354,336,385,385,354,429,354,398,336,\
336,336,354,354,354,354,354,354,354,354,\
354,354,354,354,367,442,336,336,336,336,\
336,398,367,336,336,336,336,336,336,367,\
367,336,336,367,367,367,367,367,385,385,\
336,336,336,336,336,336,336,336,380,367,\
367,336,336,336,336,336,336,336,336,336,\
336,380,336,336,336,336,336,336,336,336,\
336,336,336,336,354,354,354,349,336,336,\
336,336,398,367,380,336,336,336,336,336,\
442,442,367,349,349,349,367,336,336,336,\
336,336,336,336,336,367,367,367,336,367,\
349,349,349,411,411,336,336,380,380,380,\
336,336,349,349,336,336,336,336,336,504,\
380,336,336,349,349,349,336,336,336,336,\
336,336,336,336,336,336,336,336,380,380,\
380,380,349,349,349,349,411,380,380,380,\
336,349,349,349,349,349,336,336,349,349,\
349,349,349,349,349,349,349,349,411,411,\
349,349,349,349,367,367,367,349,349,411,\
367,380,349,349,362,362,349,336,362,380,\
380,362,362,362,380,336,336,336,336,331,\
331,380,349,349,349,349,349,349,380,424,\
380,349,349,424,362,362,424,349,349,331,\
393,393,393,393,331,331,331,349,362,349,\
349,349,349,349,349,349,349,349,349,349,\
349,349,349,349,362,331,331,331,331,331,\
331,331,331,393,393,362,362,362,331,331,\
331,331,331,331,424,424,331,331,331,331,\
362,362,362,362,331,331,331,362,349,349,\
331,331,362,362,362,362,362,362,362,362,\
362,362,380,380,380,380,331,331,331,331,\
331,331,331,331,331,362,362,331,375,375,\
362,362,331,331,331,331,331,331,468,331,\
331,331,331,331,331,331,331,331,331,393,\
375,331,331,331,331,331,331,331,331,393,\
331,331,331,331,331,331,331,349,349,349,\
349,344,344,344,362,362,331,331,331,331,\
393,362,331,331,437,331,331,331,331,331,\
331,331,393,331,437,437,331,362,362,362,\
344,344,344,344,331,331,362,362,362,331,\
331,331,331,331,331,331,331,331,331,331,\
331,375,362,362,362,362,362,331,331,362,\
362,406,344,344,344,344,406,406,331,331,\
331,375,375,331,344,331,331,331,331,331,\
437,375,331,331,331,331,331,468,344,344,\
344,344,331,331,375,375,344,344,331,331,\
331,331,331,331,331,331,331,331,331,331,\
331,331,331,331,375,375,375,375,375,375,\
393,344,344,344,344,344,344,344,344,406,\
388,388,331,331,375,344,344,344,406,331,\
331,344,344,344,344,344,406,388,344,344,\
344,344,344,344,344,406,406,344,344,344,\
344,362,362,357,344,344,362,375,344,344,\
344,357,344,344,344,344,450,357,450,450,\
375,375,357,357,357,357,357,344,331,331,\
331,331,331,326,375,326,344,344,344,344,\
344,344,344,344,344,344,344,375,375,375,\
419,375,375,375,375,344,344,419,357,344,\
344,344,388,388,388,388,388,388,326,326,\
344,344,357,357,344,344,344,344,344,344,\
344,525,344,388,344,344,344,344,344,357,\
344,344,344,344,344,344,326,326,326,326,\
326,326,326,326,388,331,357,357,357,357,\
357,326,326,326,326,326,326,326,326,401,\
419,419,326,326,357,357,357,357,357,326,\
326,326,357,357,357,344,326,344,326,326,\
326,357,357,357,357,357,357,357,357,357,\
357,419,357,357,357,375,375,375,375,388,\
326,326,326,326,326,326,326,326,357,375,\
357,357,370,357,326,326,326,326,326,326,\
326,326,326,326,326,326,326,344,344,326,\
326,326,326,326,326,326,326,326,326,326,\
388,388,388,388,370,370,370,326,326,326,\
326,326,326,326,326,326,388,388,326,326,\
326,326,326,326,326,344,344,344,344,344,\
344,339,339,326,339,339,357,326,326,326,\
326,326,326,326,326,326,326,388,326,357,\
357,357,326,432,326,326,326,326,326,326,\
326,326,326,326,326,326,326,326,326,326,\
326,388,388,326,326,357,432,370,339,326,\
357,401,401,339,339,339,339,357,357,326,\
326,326,357,357,357,344,326,326,326,326,\
326,326,326,326,326,326,326,326,326,326,\
326,370,370,357,357,357,357,357,357,357,\
370,357,326,326,326,326,326,326,357,326,\
401,445,339,339,339,339,339,339,339,401,\
326,326,326,326,326,326,326,326,326,370,\
370,326,370,326,326,326,326,339,339,339,\
339,326,326,326,326,326,326,326,326,326,\
370,326,326,326,326,326,326,326,339,339,\
370,370,339,339,339,326,326,326,326,326,\
326,326,326,326,326,326,326,326,326,326,\
326,326,339,370,370,370,370,370,370,370,\
370,370,383,401,388,388,388,339,339,339,\
339,339,339,339,339,401,383,370,339,383,\
326,445,326,370,370,370,339,326,326,339,\
339,370,339,339,326,326,326,476,339,339,\
339,339,339,339,339,383,339,339,339,339,\
339,339,339,339,339,339,339,401,339,339,\
339,401,339,357,357,357,357,357,352,352,\
339,370,339,339,339,339,339,339,383,352,\
339,339,339,432,339,339,339,339,445,445,\
445,383,326,370,370,370,352,352,352,352,\
339,339,326,326,326,326,370,370,476,339,\
339,383,339,339,339,339,339,339,339,339,\
339,339,339,339,326,370,370,370,370,370,\
370,370,339,339,370,370,339,414,352,414,\
414,339,339,339,339,339,339,383,383,383,\
383,383,339,339,339,339,352,352,445,339,\
339,339,339,339,339,339,339,507,383,339,\
339,339,339,339,339,352,352,352,352,383,\
352,352,339,339,352,339,339,339,339,339,\
339,339,339,339,339,339,339,339,352,339,\
383,383,383,383,326,326,352,352,352,352,\
352,352,414,383,414,414,383,383,339,352,\
352,352,352,352,352,352,339,339,339,352,\
352,352,352,352,352,352,352,352,352,352,\
352,352,352,352,414,414,352,352,352,352,\
370,370,370,383,365,352,352,414,383,383,\
352,352,352,352,352,365,352,352,458,352,\
339,339,383,383,383,352,365,365,365,365,\
383,383,334,339,339,339,339,339,334,334,\
334,383,383,334,383,352,352,352,352,334,\
383,427,383,383,383,352,427,427,365,352,\
352,352,352,396,396,396,334,334,334,334,\
352,352,352,352,352,352,352,352,352,352,\
352,365,365,365,352,352,352,352,352,352,\
352,352,352,352,365,352,352,352,352,440,\
334,334,334,334,334,334,334,396,339,396,\
396};
static unsigned long pre_num[pre_guess_size]=\
{52527,60975,63387,71310,71311,74791,74793,77031,78791,87087,\
88059,91463,95081,99067,99721,100167,105054,105055,106239,115547,\
118187,118191,121950,121951,123391,126774,126775,128251,128743,129991,\
130631,132089,132961,135111,137195,140073,140479,141759,142587,142620,\
142621,142622,144283,146599,148601,149582,149583,149586,149587,150015,\
150251,154062,154063,154345,156159,157582,157583,159359,160411,162601,\
164521,166011,166015,166491,169033,171001,171003,171007,171657,173321,\
174174,174175,176118,176119,177281,177287,178075,180463,182926,182927,\
185087,186763,187303,187305,189855,190161,190162,190163,191559,192231,\
192377,192379,192711,192751,193115,194031,194987,195465,195947,198134,\
198135,198523,199442,199443,199449,200334,200335,202471,202667,205417,\
205793,206463,206847,210108,210109,210110,211051,212478,212479,213881,\
216367,216801,219361,219899,221353,221991,225023,225377,226587,228001,\
228009,228399,230631,231094,231095,232233,233191,234239,234825,236374,\
236375,236382,236383,237433,239039,240617,243900,243901,243902,243951,\
246782,246783,247387,249017,249019,249023,249737,250363,253548,253549,\
253550,254911,256502,256503,256505,256511,257001,257486,257487,259982,\
259983,260847,261262,261263,263103,264178,264179,264697,265922,265923,\
265931,267113,269083,269961,270222,270223,270271,270695,270847,273889,\
274390,274391,275239,277615,277631,278311,280145,280146,280147,280955,\
280958,280959,281401,281659,283305,283518,283519,284783,285174,285175,\
285240,285242,285244,285245,287339,287343,288297,288347,288489,288566,\
288567,288569,288615,289067,289127,289673,290727,291047,292481,293198,\
293199,293921,295131,295137,296391,297202,297203,297785,298843,299164,\
299165,299166,299172,299173,299174,300030,300031,300502,300503,302719,\
303103,303707,304001,308071,308124,308125,308126,308690,308691,309643,\
309695,310271,310921,312318,312319,312603,313099,315164,315165,315166,\
315177,316577,318718,318719,320263,320822,320823,321003,324551,325201,\
325202,325203,329042,329043,329151,329849,332022,332023,332025,332030,\
332031,332982,332983,332987,333817,336199,337535,338065,338066,338067,\
339881,341671,342002,342003,342006,342007,342014,342015,342127,342599,\
343314,343315,345947,346642,346643,348348,348349,348350,349787,351279,\
351359,351679,352236,352237,352238,352929,354303,354562,354563,354567,\
354574,354575,355143,355591,356150,356151,358063,358559,358777,359967,\
360297,360303,360361,360926,360927,361129,362343,365185,365852,365853,\
365854,365927,366985,369087,369567,370153,370155,370174,370175,371081,\
373526,373527,373529,373535,373543,374606,374607,374610,374611,375201,\
375545,375559,376603,376767,376831,377739,378025,379207,379710,379711,\
380233,380322,380323,380324,380325,380326,381727,382367,383118,383119,\
384447,384462,384463,384754,384755,384758,384759,384767,384859,385422,\
385423,385502,385503,386230,386231,388062,388063,388155,389191,389871,\
389974,389975,390930,390931,391271,391894,391895,393511,393967,394651,\
394655,396268,396269,396270,397046,397047,398247,398457,398884,398885,\
398886,398887,398897,398898,398899,400041,400668,400669,400670,400671,\
401151,403625,404137,404942,404943,405334,405335,405407,405447,405483,\
406043,406271,406891,410011,410761,410833,410834,410835,411586,411587,\
412857,412859,412926,412927,413694,413695,414561,416367,416423,416425,\
416447,416703,417465,417467,418431,420216,420218,420220,420221,420235,\
421433,421435,421438,421439,422102,422103,422489,422505,423679,424956,\
424957,424958,425278,425279,425503,426651,426655,427017,427175,427762,\
427763,427864,427866,427868,427869,431009,431015,431017,431899,432446,\
432447,432521,432734,432735,432811,432849,432850,432851,432854,432855,\
432923,432967,432993,433601,433602,433603,433691,434223,434510,434511,\
434919,436091,436571,436674,436675,437247,437257,438699,438722,438723,\
439327,439798,439799,440859,440881,440882,440883,442697,442706,442707,\
443017,443071,443977,443982,443983,444587,444591,444985,445089,445095,\
445804,445805,445806,446678,446679,447801,448265,448743,448748,448749,\
448750,448758,448759,448760,448762,448764,448765,449479,450027,450046,\
450047,450651,450753,450754,450755,453174,453175,454079,454383,454655,\
455561,455659,456002,456003,456009,456018,456019,456169,456798,456799,\
456891,457753,461262,461263,462107,462188,462189,462190,463036,463037,\
463038,464415,464465,464466,464467,464543,465407,466382,466383,466923,\
467739,468478,468479,468905,469649,469650,469651,469663,472748,472749,\
472750,472764,472765,472766,472767,474121,474866,474867,477417,478078,\
478079,478369,478959,479931,479935,479983,480395,480481,481215,481234,\
481235,481505,481959,482239,485887,486827,486913,487039,487800,487802,\
487804,487805,487902,487903,488127,489313,492571,493537,493564,493565,\
493566,493727,494774,494775,498034,498035,498038,498039,498046,498047,\
498057,499474,499475,499481,499647,500271,500726,500727,500731,500745,\
502137,502441,504033,504299,505609,506281,506303,506977,506983,507096,\
507097,507098,507100,507101,507111,507903,508399,508969,509822,509823,\
510825,511935,512507,512617,513004,513005,513006,513010,513011,513022,\
513023,513145,513191,513897,513899,514002,514003,514671,514972,514973,\
514974,515239,517417,517543,518921,519871,519964,519965,519966,520683,\
521241,521694,521695,522524,522525,522526,524681,525289,525543,526201,\
526206,526207,526919,527039,527131,527519,528356,528357,528358,528895,\
529394,529395,530727,530943,531455,531844,531845,531846,531849,531851,\
531862,531863,531865,532715,533387,534225,534226,534227,536319,537095,\
537839,538166,538167,538849,539922,539923,539951,540444,540445,540446,\
540455,540542,540543,541390,541391,541694,541695,542521,543515,545607,\
546681,547681,547777,547778,547779,548780,548781,548782,548891,550478,\
550479,550569,551593,553631,554143,554351,555111,555230,555231,555233,\
555262,555263,555739,556622,556623,560290,560291,560292,560293,560294,\
560295,560303,560313,560315,560575,561910,561911,561913,561916,561917,\
561918,562802,562803,563318,563319,563323,563339,564905,565151,565247,\
566609,566610,566611,566955,567036,567037,567038,567337,567655,567675,\
568807,568811,568873,569566,569567,569595,570348,570349,570350,570480,\
570484,570485,570488,570490,571551,572591,573551,573855,574678,574679,\
574683,574686,574687,574689,575079,575865,576571,576594,576595,576671,\
576694,576695,576978,576979,577081,577132,577133,577134,577138,577139,\
577151,577230,577231,577289,578134,578135,578137,578254,578255,579007,\
579303,579327,579346,579347,579687,581454,581455,582094,582095,582233,\
582639,583009,583787,584007,584807,584962,584963,584967,585327,585769,\
586396,586397,586398,586907,587841,587842,587843,587899,587935,590262,\
590263,590267,590274,590275,590689,590761,590951,591207,591969,591975,\
591977,591983,592782,592783,593023,593313,594404,594405,594406,595570,\
595571,596415,597231,597243,597371,597686,597687,598255,598328,598330,\
598331,598332,598333,598344,598345,598346,598348,598349,598353,598375,\
599305,600060,600061,600062,600063,601003,601004,601005,601006,601007,\
601327,601727,601959,604233,605438,605439,606183,606206,606207,607414,\
607415,607545,608002,608003,608007,608011,608025,608111,608171,608225,\
608415,609063,609065,609407,610215,610337,610863,611455,615017,616142,\
616143,616248,616250,616252,616253,617380,617381,617382,617767,619286,\
619287,619289,619387,619390,619391,620542,620543,621842,621843,623643,\
624495,624551,624635,624636,624637,624638,624639,624747,625055,625206,\
625207,626198,626199,626201,626217,626331,627647,630328,630330,630332,\
630333,630353,630354,630355,630363,632161,632347,633154,633155,633159,\
635519,637436,637437,637438,637825,638255,638635,639913,639977,639983,\
640047,640526,640527,640539,640641,640763,640795,641644,641645,641646,\
642006,642007,642075,642985,642987,647849,649051,649102,649103,649215,\
649217,649385,650402,650403,650404,650405,650406,650537,651335,652379,\
652417,652527,653031,653739,655871,656155,656761,657903,658049,658084,\
658085,658086,658302,658303,659698,659699,664044,664045,664046,664050,\
664051,664060,664061,664062,664063,665215,665964,665965,665966,665974,\
665975,665979,667375,667634,667635,667641,667643,669921,672043,672398,\
672399,673115,674031,674145,674219,675041,675070,675071,675969,675977,\
676129,676130,676131,676132,676133,676134,677865,678511,678625,679762,\
679763,680095,680703,680991,681099,681119,681575,683342,683343,683371,\
683489,683947,684004,684005,684006,684012,684013,684014,684028,684029,\
684030,684193,684254,684255,685195,685198,685199,685337,686527,686628,\
686629,686630,686985,687279,687871,689131,689889,690057,690535,690975,\
691894,691895,693161,693284,693285,693286,694987,695593,696623,696696,\
696698,696700,696701,696811,696815,698111,699574,699575,700075,700385,\
701595,701599,701601,701607,701609,702558,702559,702715,702718,702719,\
702841,703231,703358,703359,704472,704474,704476,704477,704495,704623,\
705193,705858,705859,707995,708606,708607,709124,709125,709126,709131,\
709134,709135,709148,709149,709150,709151,709153,709159,710286,710287,\
711182,711183,712299,712300,712301,712302,712683,713575,716126,716127,\
716743,717118,717119,717543,717554,717555,718439,718465,719897,719903,\
719934,719935,719975,720593,720594,720595,720606,720607,720722,720723,\
720795,720859,720895,721823,721852,721853,721854,722258,722259,722335,\
722715,722939,723359,723361,724686,724687,726811,728831,728859,730183,\
730241,730369,730370,730371,730559,731704,731706,731708,731709,731854,\
731855,732191,732399,733927,733970,733971,734043,734091,735457,735679,\
737371,738174,738175,738857,739134,739135,739143,740143,740167,740295,\
740306,740307,740310,740311,740348,740349,740350,740591,740985,742162,\
742163,742183,745711,747052,747053,747054,747057,747058,747059,747070,\
747071,747086,747087,747433,747519,749212,749213,749214,749217,749220,\
749221,749222,749223,749227,749471,750402,750403,750407,751090,751091,\
751097,751099,751118,751119,753206,753207,753534,753535,753662,753663,\
755478,755479,755481,755943,756049,756050,756051,756449,756873,756903,\
757167,757255,758409,758414,758415,758491,758497,758511,759420,759421,\
759422,759455,760465,760466,760467,760475,760644,760645,760646,760648,\
760650,760651,760652,760653,760667,761855,761983,762599,763454,763455,\
764734,764735,765567,766191,766236,766237,766238,766249,767903,768761,\
768793,768795,768799,768894,768895,768924,768925,768926,768927,769305,\
769441,769508,769509,769510,769516,769517,769518,769534,769535,769641,\
769718,769719,769767,769787,769791,770155,770815,770844,770845,770846,\
770849,771004,771005,771006,772007,772009,772455,772460,772461,772462,\
772859,773247,773871,774559,775035,775273,776124,776125,776126,776310,\
776311,776315,777327,777345,778382,778383,779079,779742,779743,779807,\
779948,779949,779950,780135,780391,781025,781860,781861,781862,782535,\
782542,782543,782587,783739,783775,783788,783789,783790,783865,783867,\
783913,785691,787017,787022,787023,787033,787071,787585,787681,787934,\
787935,788315,789291,789295,789302,789303,789310,789311,790377,790379,\
790431,790555,790559,790697,791279,791803,792536,792538,792540,792541,\
792735,793343,794092,794093,794094,795295,796091,796095,796287,796415,\
796494,796495,796519,796671,796914,796915,797183,797673,797768,797770,\
797772,797773,797774,797775,797777,797787,797793,797794,797795,797796,\
797797,797798,797803,797833,799023,799073,799983,800081,800082,800083,\
801147,801336,801337,801338,801339,801340,801341,801342,801343,801769,\
802302,802303,804479,805375,805643,806759,807250,807251,807327,808274,\
808275,809884,809885,809886,809927,809979,810399,810603,810668,810669,\
810670,810681,810683,810687,810699,810814,810815,810894,810895,810966,\
810967,812086,812087,812251,812542,812543,813055,813307,813782,813783,\
815271,815273,815995,816747,817663,818411,818943,819967,820022,820023,\
821522,821523,821666,821667,821668,821669,821670,822139,822895,823172,\
823173,823174,823179,823337,823689,824347,825627,825714,825715,825718,\
825719,825799,825849,825852,825853,825854,825855,827388,827389,827390,\
827503,829119,829122,829123,829543,829819,830447,831215,831527,832667,\
832734,832735,832839,832846,832847,832849,832850,832851,832894,832895,\
833406,833407,833609,833775,834930,834931,834934,834935,834939,836862,\
836863,837799,838683,839547,840432,840436,840437,840440,840442,840443,\
840455,840470,840471,840473,840475,840863,842866,842867,842870,842871,\
842875,842876,842877,842878,842881,843129,844204,844205,844206,844207,\
844647,844977,844978,844979,844985,844987,845009,845010,845011,845223,\
847358,847359,847727,847871,849912,849914,849916,849917,850433,850556,\
850557,850558,850975,851006,851007,851483,851497,851513,851871,851913,\
852075,853211,853217,853255,853275,853302,853303,853310,853311,854034,\
854035,854191,854350,854351,854393,855524,855525,855526,855535,855583,\
855728,855732,855733,855736,855738,855745,855751,855753,856009,856551,\
857313,857327,858887,860327,860779,860783,861537,861543,861865,862018,\
862019,862025,862030,862031,862034,862035,862619,863798,863799,864559,\
864857,864892,864893,864894,864895,864955,865007,865023,865042,865043,\
865401,865468,865469,865470,865622,865623,865627,865698,865699,865700,\
865701,865702,865708,865709,865710,865727,865846,865847,865934,865935,\
865986,865987,866011,866017,866425,867202,867203,867204,867205,867206,\
867207,867382,867383,867687,868446,868447,868511,868827,868839,868843,\
868921,868955,868991,869020,869021,869022,869023,869467,869531,869838,\
869839,869889,870427,871915,872182,872183,872731,873033,873142,873143,\
873147,873151,873195,873199,873348,873349,873350,873355,873519,873959,\
874011,874494,874495,874514,874515,874873,875681,876011,876015,876513,\
877211,877398,877399,877444,877445,877446,877451,877737,877991,878654,\
878655,879195,879596,879597,879598,879975,880347,880353,880361,880411,\
881707,881718,881719,881762,881763,881764,881765,881766,881849,881851,\
881903,883903,883995,885393,885394,885395,885401,885412,885413,885414,\
885417,885435,885787,885807,886034,886035,886142,886143,886427,886811,\
886855,886953,887953,887954,887955,887963,887964,887965,887966,887975,\
889174,889175,889177,889179,889182,889183,889209,889225,889255,889371,\
889375,889535,889833,889887,889970,889971,889983,890178,890179,890190,\
890191,890779,891608,891610,891612,891613,891627,893356,893357,893358,\
894623,894697,895602,895603,895847,895865,895867,895881,896057,896059,\
896530,896531,897383,897486,897487,897496,897497,897498,897500,897501,\
897511,897516,897517,897518,897520,897524,897525,897528,897529,897530,\
897537,897563,898075,898855,898958,898959,900054,900055,900092,900093,\
900094,900095,900511,900735,901291,901302,901303,901505,901506,901507,\
901508,901509,901510,901511,901531,901991,902591,902939,904681,904833,\
904959,906175,906271,906348,906349,906350,906793,907129,907243,908158,\
908159,908319,908766,908767,909275,909310,909311,910107,911122,911123,\
911161,911227,911318,911319,911359,911929,912004,912005,912006,912011,\
912017,912018,912019,912036,912037,912038,912103,912167,912257,912338,\
912339,912511,912623,913593,913595,913596,913597,913598,913782,913783,\
914111,914971,915323,915369,915505,915506,915507,916295,917161,917183,\
917995,918841,919419,919791,919851,920071,920713,921447,922524,922525,\
922526,922875,922983,924139,924214,924215,924376,924378,924380,924381,\
924907,925659,926072,926074,926076,926077,926649,926651,927003,927457,\
927487,928191,928830,928831,928875,928930,928931,928932,928933,928934,\
929081,929086,929087,929863,930043,930814,930815,932764,932765,932766,\
932767,932779,933433,933547,933846,933847,933999,934299,935465,935478,\
935479,936743,936745,936751,936775,936807,936827,936953,936956,936957,\
936958,936959,937121,937583,937599,937641,937810,937811,938143,939298,\
939299,939300,939301,939302,939307,939326,939327,939497,940257,941145,\
941471,942571,943515,943519,943791,943899,943975,943993,943995,944491,\
944809,945403,945496,945498,945499,945500,945501,945513,945528,945530,\
945531,945532,945533,945534,945535,945537,945545,945579,946119,946591,\
946623,947049,948242,948243,948519,948521,949732,949733,949734,949735,\
949739,949743,950943,951433,952479,953279,954834,954835,955657,956156,\
956157,956158,956187,956738,956739,957383,957918,957919,957953,959862,\
959863,959870,959871,959913,959935,959966,959967,959975,960071,960790,\
960791,960793,960807,960809,960962,960963,961145,961193,962430,962431,\
962468,962469,962470,962631,962667,963010,963011,963113,963918,963919,\
964287,964478,964479,964481,966247,966249,969081,970587,970599,971247,\
971774,971775,973577,973654,973655,973823,973825,973826,973827,973831,\
974078,974079,974751,975600,975604,975605,975608,975610,975804,975805,\
975806,976254,976255,977003,978151,978569,978626,978627,978791,979547,\
980609,980905,982663,983161,983807,984233,985142,985143,985513,986855,\
986857,986863,986889,987074,987075,987081,987128,987130,987132,987133,\
987454,987455,987739,989547,989548,989549,989550,989551,989577,992895,\
994281,994395,994495,995967,996068,996069,996070,996076,996077,996078,\
996091,996092,996093,996094,996095,996114,996115,996577,997231,997823,\
998948,998949,998950,998959,998961,998962,998963,998969,999271,999294,\
999295};

#define schache_size  0x400UL
static short precomputed_chache[schache_size] = \
{1,8,6,17,20,15,10,18,13,21,8,16,24,112,\
19,107,27,14,22,35,110,30,17,105,25,25,12,113,33,33,20,108,28,28,15,103,\
116,15,23,36,23,111,10,31,31,93,18,106,119,26,26,88,39,101,114,70,13,34,\
21,34,96,47,109,47,122,29,29,42,91,42,16,104,117,117,24,16,37,86,37,55,\
99,24,112,68,50,125,32,81,32,32,19,94,45,45,107,45,120,120,27,120,19,40,\
27,89,40,40,14,102,27,53,115,71,53,14,35,128,84,128,35,53,22,97,22,48,\
48,66,110,48,123,123,30,79,123,22,30,43,30,92,17,43,43,61,105,43,30,118,\
118,56,74,118,17,43,38,38,25,87,131,38,38,56,25,100,25,144,51,25,113,69,\
113,51,12,126,126,126,33,82,126,33,33,51,46,46,95,46,20,46,20,46,64,59,\
108,46,33,121,121,121,59,77,28,121,20,20,28,41,41,134,90,134,134,41,41,\
33,59,54,103,41,28,28,116,54,28,54,72,98,116,54,15,41,129,129,36,129,36,\
85,23,129,36,28,36,54,49,23,98,142,49,142,49,98,23,49,111,67,62,36,49,\
62,36,124,124,62,124,124,31,80,31,124,31,23,23,49,44,137,44,31,93,44,137,\
31,44,88,44,44,18,62,57,31,106,44,31,31,119,31,57,119,119,57,75,75,26,\
119,57,70,18,44,132,39,39,70,132,132,88,132,26,132,39,39,31,31,57,132,52,\
26,101,39,145,101,26,145,52,52,114,26,52,145,70,96,65,114,52,65,65,39,127,\
39,127,127,34,127,127,65,83,171,34,127,34,65,26,26,34,52,47,47,21,47,34,\
140,96,47,140,21,47,96,91,47,47,140,21,65,109,60,34,153,47,60,34,34,122,\
153,34,60,122,122,122,60,29,78,78,104,122,73,60,21,21,73,47,135,42,135,42,\
42,29,135,135,42,91,135,29,135,42,86,42,42,42,34,60,60,16,55,29,148,104,\
42,148,29,29,179,148,29,55,148,117,29,117,55,148,47,73,99,68,117,55,117,\
68,55,16,42,130,130,37,130,130,68,130,117,130,37,86,130,174,86,130,37,37,\
37,37,29,29,29,55,130,50,50,24,143,50,37,99,143,99,50,24,143,24,37,50,\
99,94,24,50,50,143,42,68,94,112,63,112,37,156,63,50,63,37,37,125,37,156,\
125,125,63,125,125,32,125,63,94,81,169,81,32,125,76,76,63,24,169,24,24,32,\
50,138,138,45,138,45,45,32,76,138,32,94,45,94,138,19,32,138,94,45,89,45,\
45,45,138,37,37,63,63,19,58,107,32,151,58,45,58,151,32,32,58,182,151,120,\
32,58,58,120,120,32,58,58,89,151,76,76,50,102,120,120,71,58,58,19,71,58,\
71,45,164,133,133,40,133,133,133,40,71,133,133,27,133,40,71,89,133,177,27,\
133,89,40,84,40,177,40,32,40,32,32,84,58,133,53,53,27,146,146,53,102,40,\
102,146,27,102,53,177,146,102,27,53,53,146,102,53,27,53,53,53,115,146,45,\
27,71,97,115,66,115,159,40,115,53,66,53,66,14,40,40,115,128,40,159,128,\
128,97,66,66,128,115,35,128,35,66,97,128,84,172,84,35,128,35,79,128,35,\
66,27,27,35,27,27,79,53,128,141,48,48,53,141,141,48,141,35,35,97,141,35,\
141,48,172,97,141,22,97,35,141,48,97,48,92,22,48,48,48,48,141,40,22,66,\
92,66,141,61,154,110,35,110,154,61,61,48,61,154,35,35,110,61,35,123,154,\
123,35,123,61,61,154,123,61,35,123,61,61,92,123,79,167,79,79,30,105,123,\
74,123,74,61,61,22,167,74,22,22,74,48,48,30,136,136,74,43,136,136,43,43,\
105,74,74,136,136,30,136,92,43,74,43,136,74,180,30,136,43,92,136,43,87,43,\
43,43,43,35,136,35,180,35,61,61,61,136,149,56,149,30,30,105,149,56,56,43,\
56,105,149,30,105,105,56,30,180,149,149,118,30,56,43,56,149,105,118,30,149,\
56,56,56,87,118,149,74,48,30,48,100,100,118,69,118,69,162,43,56,118,56,69,\
17,56,69,162,43,162,43,131,131,69,43,131,131,162,131,131,38,69,69,131,131,\
118,38,131,38,69,69,38,87,131,87,175,25,87,38,87,131,38,82,38,38,175,69,\
69,30,131,38,30,38,30,82,175,56,131,144,51,51,51,56,144,25,144,51,51,100,\
38,38,82,144,175,38,100,51,82,175,82,144,100,25,25,51,38,144,144,100,51,\
51,95,25,51,51,51,51,51,51,144,113,43,25,43,69,95,69,113,64,157,157,157,\
38,64,113,157,51,64,64,157,64,157};

#ifndef _NO_CHACHE_
#define dchache_size 0x0007FFFFUL   
#else
#define dchache_size 0x400UL 
#endif

static short dynamic_chache[dchache_size+1];
static short* chache[2]; 
#define stack_len 0x15E
short running_stack_len[stack_len];
ultype running_stack_num[stack_len];

#define count_trailing_zeros(v) Mod37BitPosition[(-(v) & (v)) % 37]
#define get_key(index, num) \
    (index == 0 ? ((num) >> 1) : (((num) >> 1)-schache_size))    

void update_hash(short hss_len) {
    short stack_ptr = 0;
    unsigned long key = 0;
    while((running_stack_len[stack_ptr] != -1)) {
        key = get_key(1, running_stack_num[stack_ptr]);
        if(key <= dchache_size) {
            chache[1][key] = hss_len-running_stack_len[stack_ptr];
        }
        stack_ptr++;
    }
}

short Cal_hss_length(ultype num) {
    short hss_len = 0;
    unsigned short index = 0;
    unsigned long key = 0;
    short stack_ptr = -1;
    while(stack_ptr < stack_len-1) {
        unsigned short trailing_zeros = count_trailing_zeros(num);
        num >>= trailing_zeros; 
        hss_len += trailing_zeros; 
        index = ((num & 0xFFFFF800UL) >> count_trailing_zeros(num & 0xFFFFF800UL))  & 0x01UL;
        key = get_key(index, num);
        if( (key <= dchache_size) && chache[index][key] != 0) {
            hss_len += chache[index][key];
            break;
        }
        stack_ptr++;
        running_stack_num[stack_ptr] = num;
        running_stack_len[stack_ptr] = hss_len;
        hss_len++;
        num = (num << 1) + num + 1;
    }
    stack_ptr++;
    running_stack_len[stack_ptr] = -1;
    update_hash(hss_len);
    return hss_len;
}

short binary_search(unsigned long A [], unsigned long key, short imin, short imax) {
  while (imax >= imin) {
      int imid = imin + ((imax - imin) / 2);
      if(A[imid] <  key)
        imin = imid + 1;
      else if (A[imid] > key )
        imax = imid - 1;
      else
        return imid;
  }
  return -1;
}

short binary_search_2(unsigned long key, short imin, short imax, bool MINIMA = true) {
    while (imax >= imin) {
        int imid = imin + ((imax - imin) / 2);
        if(pre_num[imid] <  key)
            imin = imid + 1;
        else if (pre_num[imid] > key )
            imax = imid - 1;
        else
            return imid;
    }
    return MINIMA ? imin : imax;
}

void sub_array(unsigned long min, unsigned max, short& start, short& end) {
    if(min > pre_num[pre_guess_size-1])
        start = -1;
    else if(min <= pre_num[0])
        start = 0;
    else
        start = binary_search_2(min, 0, pre_guess_size-1);

    if(max >= pre_num[pre_guess_size-1])
        end = pre_guess_size-1;
    else if(max < pre_num[0])
        end = -1;
    else
        end = binary_search_2(max, 0, pre_guess_size-1, false);
}

short pre_guess(unsigned long min, unsigned long max) {
    short min_index = 0;
    short max_index = 0;
    sub_array(min, max, min_index, max_index);
    if((min_index == max_index) && min <= (pre_num[min_index]) && (max >= pre_num[max_index]))
        return pre_len[min_index];
    else if((min_index >= 0) && (min_index < max_index))
        return *max_element(pre_len+min_index, pre_len+max_index+1);
    else
        return 0;
}

short Max_hss_length(ultype num,  long len) {
    if (num == 0) return 0;
    short max_sofar = 0;
    if(len == 0 && num >= pre_num[0] && num <= pre_num[pre_guess_size-1]) {
        short index = binary_search(pre_num, num, 0, pre_guess_size-1);
        if(index != (short)(-1))
            return pre_len[index];
    }
    if(len != 0) {
        max_sofar = pre_guess(num, num+len);
        if(max_sofar != 0)
            return max_sofar;
    }
    while (len-- >= 0)
            max_sofar = Max(max_sofar, Cal_hss_length(num++));
    return max_sofar;
}

int main() {
    ultype start=0, end=0;
    short max_len=0;
    memset(dynamic_chache, 0 , dchache_size+1);
    chache[0] = precomputed_chache;
    chache[1] = dynamic_chache;
    while (scanf("%lu %lu", &start, &end ) != EOF) {
        max_len = Max_hss_length(Min(start, end), Abs(start-end));
        printf("%lu %lu %hi\n", start, end, max_len);
    }
    return 0;
}

Afterthoughts -

The above implementation gets the better timing with the idea that I will not compute the length, Even if you force me to compute I will not hit 3n+1 path. 
There are 344030 elements who have cycle length upto 100
There are 530365 elements who have cycle length from 101 to 200
There are 119919 elements who have cycle length from 201 to 300
There are 5574 elements who have cycle length from 301 to 400
There are 106 elements who have cycle length from 401 to 500
There are only 4 elements who have cycle length greater than 500
The above piece of code is optimized for cycle length greater than 325 and less than 100.
Only 6 kb more space is left in source to achieve 0.000 timing.
Plenty of run time memory is left, I am using only 600 kb, more than 1 MB is left.
The above algorithm takes maximum 85 iterations of 3n+1 path in worst case to get hailstone sequence length.
The optimization I am looking for is around the elements having cycle length 200-324

Give your try and do share -