username1565/BBP_NthHexDigitOfPI.html

## BBP_NthHexDigitOfPI.html
Open this in new tab, and see console.log (F12 button);
<script>
//first 8336 hexadecimal digits of pi:	https://gist.github.com/retrohacker/e5fff72b7b75ee058924

//multiline string:
var pi_test_string = function(){/*
243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89
452821E638D01377BE5466CF34E90C6CC0AC29B7C97C50DD3F84D5B5B5470917
9216D5D98979FB1BD1310BA698DFB5AC2FFD72DBD01ADFB7B8E1AFED6A267E96
BA7C9045F12C7F9924A19947B3916CF70801F2E2858EFC16636920D871574E69
A458FEA3F4933D7E0D95748F728EB658718BCD5882154AEE7B54A41DC25A59B5
9C30D5392AF26013C5D1B023286085F0CA417918B8DB38EF8E79DCB0603A180E
6C9E0E8BB01E8A3ED71577C1BD314B2778AF2FDA55605C60E65525F3AA55AB94
5748986263E8144055CA396A2AAB10B6B4CC5C341141E8CEA15486AF7C72E993
B3EE1411636FBC2A2BA9C55D741831F6CE5C3E169B87931EAFD6BA336C24CF5C
7A325381289586773B8F48986B4BB9AFC4BFE81B6628219361D809CCFB21A991
487CAC605DEC8032EF845D5DE98575B1DC262302EB651B8823893E81D396ACC5
0F6D6FF383F442392E0B4482A484200469C8F04A9E1F9B5E21C66842F6E96C9A
670C9C61ABD388F06A51A0D2D8542F68960FA728AB5133A36EEF0B6C137A3BE4
BA3BF0507EFB2A98A1F1651D39AF017666CA593E82430E888CEE8619456F9FB4
7D84A5C33B8B5EBEE06F75D885C12073401A449F56C16AA64ED3AA62363F7706
1BFEDF72429B023D37D0D724D00A1248DB0FEAD349F1C09B075372C980991B7B
25D479D8F6E8DEF7E3FE501AB6794C3B976CE0BD04C006BAC1A94FB6409F60C4
5E5C9EC2196A246368FB6FAF3E6C53B51339B2EB3B52EC6F6DFC511F9B30952C
CC814544AF5EBD09BEE3D004DE334AFD660F2807192E4BB3C0CBA85745C8740F
D20B5F39B9D3FBDB5579C0BD1A60320AD6A100C6402C7279679F25FEFB1FA3CC
8EA5E9F8DB3222F83C7516DFFD616B152F501EC8AD0552AB323DB5FAFD238760
53317B483E00DF829E5C57BBCA6F8CA01A87562EDF1769DBD542A8F6287EFFC3
AC6732C68C4F5573695B27B0BBCA58C8E1FFA35DB8F011A010FA3D98FD2183B8
4AFCB56C2DD1D35B9A53E479B6F84565D28E49BC4BFB9790E1DDF2DAA4CB7E33
62FB1341CEE4C6E8EF20CADA36774C01D07E9EFE2BF11FB495DBDA4DAE909198
EAAD8E716B93D5A0D08ED1D0AFC725E08E3C5B2F8E7594B78FF6E2FBF2122B64
8888B812900DF01C4FAD5EA0688FC31CD1CFF191B3A8C1AD2F2F2218BE0E1777
EA752DFE8B021FA1E5A0CC0FB56F74E818ACF3D6CE89E299B4A84FE0FD13E0B7
7CC43B81D2ADA8D9165FA2668095770593CC7314211A1477E6AD206577B5FA86
C75442F5FB9D35CFEBCDAF0C7B3E89A0D6411BD3AE1E7E4900250E2D2071B35E
226800BB57B8E0AF2464369BF009B91E5563911D59DFA6AA78C14389D95A537F
207D5BA202E5B9C5832603766295CFA911C819684E734A41B3472DCA7B14A94A
1B5100529A532915D60F573FBC9BC6E42B60A47681E6740008BA6FB5571BE91F
F296EC6B2A0DD915B6636521E7B9F9B6FF34052EC585566453B02D5DA99F8FA1
08BA47996E85076A4B7A70E9B5B32944DB75092EC4192623AD6EA6B049A7DF7D
9CEE60B88FEDB266ECAA8C71699A17FF5664526CC2B19EE1193602A575094C29
A0591340E4183A3E3F54989A5B429D656B8FE4D699F73FD6A1D29C07EFE830F5
4D2D38E6F0255DC14CDD20868470EB266382E9C6021ECC5E09686B3F3EBAEFC9
3C9718146B6A70A1687F358452A0E286B79C5305AA5007373E07841C7FDEAE5C
8E7D44EC5716F2B8B03ADA37F0500C0DF01C1F040200B3FFAE0CF51A3CB574B2
25837A58DC0921BDD19113F97CA92FF69432477322F547013AE5E58137C2DADC
C8B576349AF3DDA7A94461460FD0030EECC8C73EA4751E41E238CD993BEA0E2F
3280BBA1183EB3314E548B384F6DB9086F420D03F60A04BF2CB8129024977C79
5679B072BCAF89AFDE9A771FD9930810B38BAE12DCCF3F2E5512721F2E6B7124
501ADDE69F84CD877A5847187408DA17BC9F9ABCE94B7D8CEC7AEC3ADB851DFA
63094366C464C3D2EF1C18473215D908DD433B3724C2BA1612A14D432A65C451
50940002133AE4DD71DFF89E10314E5581AC77D65F11199B043556F1D7A3C76B
3C11183B5924A509F28FE6ED97F1FBFA9EBABF2C1E153C6E86E34570EAE96FB1
860E5E0A5A3E2AB3771FE71C4E3D06FA2965DCB999E71D0F803E89D65266C825
2E4CC9789C10B36AC6150EBA94E2EA78A5FC3C531E0A2DF4F2F74EA7361D2B3D
1939260F19C279605223A708F71312B6EBADFE6EEAC31F66E3BC4595A67BC883
B17F37D1018CFF28C332DDEFBE6C5AA56558218568AB9802EECEA50FDB2F953B
2AEF7DAD5B6E2F841521B62829076170ECDD4775619F151013CCA830EB61BD96
0334FE1EAA0363CFB5735C904C70A239D59E9E0BCBAADE14EECC86BC60622CA7
9CAB5CABB2F3846E648B1EAF19BDF0CAA02369B9655ABB5040685A323C2AB4B3
319EE9D5C021B8F79B540B19875FA09995F7997E623D7DA8F837889A97E32D77
11ED935F166812810E358829C7E61FD696DEDFA17858BA9957F584A51B227263
9B83C3FF1AC24696CDB30AEB532E30548FD948E46DBC312858EBF2EF34C6FFEA
FE28ED61EE7C3C735D4A14D9E864B7E342105D14203E13E045EEE2B6A3AAABEA
DB6C4F15FACB4FD0C742F442EF6ABBB5654F3B1D41CD2105D81E799E86854DC7
E44B476A3D816250CF62A1F25B8D2646FC8883A0C1C7B6A37F1524C369CB7492
47848A0B5692B285095BBF00AD19489D1462B17423820E0058428D2A0C55F5EA
1DADF43E233F70613372F0928D937E41D65FECF16C223BDB7CDE3759CBEE7460
4085F2A7CE77326EA607808419F8509EE8EFD85561D99735A969A7AAC50C06C2
5A04ABFC800BCADC9E447A2EC3453484FDD567050E1E9EC9DB73DBD3105588CD
675FDA79E3674340C5C43465713E38D83D28F89EF16DFF20153E21E78FB03D4A
E6E39F2BDB83ADF7E93D5A68948140F7F64C261C94692934411520F77602D4F7
BCF46B2ED4A20068D40824713320F46A43B7D4B7500061AF1E39F62E97244546
14214F74BF8B88404D95FC1D96B591AF70F4DDD366A02F45BFBC09EC03BD9785
7FAC6DD031CB850496EB27B355FD3941DA2547E6ABCA0A9A28507825530429F4
0A2C86DAE9B66DFB68DC1462D7486900680EC0A427A18DEE4F3FFEA2E887AD8C
B58CE0067AF4D6B6AACE1E7CD3375FECCE78A399406B2A4220FE9E35D9F385B9
EE39D7AB3B124E8B1DC9FAF74B6D185626A36631EAE397B23A6EFA74DD5B4332
6841E7F7CA7820FBFB0AF54ED8FEB397454056ACBA48952755533A3A20838D87
FE6BA9B7D096954B55A867BCA1159A58CCA9296399E1DB33A62A4A563F3125F9
5EF47E1C9029317CFDF8E80204272F7080BB155C05282CE395C11548E4C66D22
48C1133FC70F86DC07F9C9EE41041F0F404779A45D886E17325F51EBD59BC0D1
F2BCC18F41113564257B7834602A9C60DFF8E8A31F636C1B0E12B4C202E1329E
AF664FD1CAD181156B2395E0333E92E13B240B62EEBEB92285B2A20EE6BA0D99
DE720C8C2DA2F728D012784595B794FD647D0862E7CCF5F05449A36F877D48FA
C39DFD27F33E8D1E0A476341992EFF743A6F6EABF4F8FD37A812DC60A1EBDDF8
991BE14CDB6E6B0DC67B55106D672C372765D43BDCD0E804F1290DC7CC00FFA3
B5390F92690FED0B667B9FFBCEDB7D9CA091CF0BD9155EA3BB132F88515BAD24
7B9479BF763BD6EB37392EB3CC1159798026E297F42E312D6842ADA7C66A2B3B
12754CCC782EF11C6A124237B79251E706A1BBE64BFB63501A6B101811CAEDFA
3D25BDD8E2E1C3C9444216590A121386D90CEC6ED5ABEA2A64AF674EDA86A85F
BEBFE98864E4C3FE9DBC8057F0F7C08660787BF86003604DD1FD8346F6381FB0
7745AE04D736FCCC83426B33F01EAB71B08041873C005E5F77A057BEBDE8AE24
55464299BF582E614E58F48FF2DDFDA2F474EF388789BDC25366F9C3C8B38E74
B475F25546FCD9B97AEB26618B1DDF84846A0E79915F95E2466E598E20B45770
8CD55591C902DE4CB90BACE1BB8205D011A862487574A99EB77F19B6E0A9DC09
662D09A1C4324633E85A1F0209F0BE8C4A99A0251D6EFE101AB93D1D0BA5A4DF
A186F20F2868F169DCB7DA83573906FEA1E2CE9B4FCD7F5250115E01A70683FA
A002B5C40DE6D0279AF88C27773F8641C3604C0661A806B5F0177A28C0F586E0
006058AA30DC7D6211E69ED72338EA6353C2DD94C2C21634BBCBEE5690BCB6DE
EBFC7DA1CE591D766F05E4094B7C018839720A3D7C927C2486E3725F724D9DB9
1AC15BB4D39EB8FCED54557808FCA5B5D83D7CD34DAD0FC41E50EF5EB161E6F8
A28514D96C51133C6FD5C7E756E14EC4362ABFCEDDC6C837D79A323492638212
670EFA8E406000E03A39CE37D3FAF5CFABC277375AC52D1B5CB0679E4FA33742
D382274099BC9BBED5118E9DBF0F7315D62D1C7EC700C47BB78C1B6B21A19045
B26EB1BE6A366EB45748AB2FBC946E79C6A376D26549C2C8530FF8EE468DDE7D
D5730A1D4CD04DC62939BBDBA9BA4650AC9526E8BE5EE304A1FAD5F06A2D519A
63EF8CE29A86EE22C089C2B843242EF6A51E03AA9CF2D0A483C061BA9BE96A4D
8FE51550BA645BD62826A2F9A73A3AE14BA99586EF5562E9C72FEFD3F752F7DA
3F046F6977FA0A5980E4A91587B086019B09E6AD3B3EE593E990FD5A9E34D797
2CF0B7D9022B8B5196D5AC3A017DA67DD1CF3ED67C7D2D281F9F25CFADF2B89B
5AD6B4725A88F54CE029AC71E019A5E647B0ACFDED93FA9BE8D3C48D283B57CC
F8D5662979132E28785F0191ED756055F7960E44E3D35E8C15056DD488F46DBA
03A161250564F0BDC3EB9E153C9057A297271AECA93A072A1B3F6D9B1E6321F5
F59C66FB26DCF3197533D928B155FDF5035634828ABA3CBB28517711C20AD9F8
ABCC5167CCAD925F4DE817513830DC8E379D58629320F991EA7A90C2FB3E7BCE
5121CE64774FBE32A8B6E37EC3293D4648DE53696413E680A2AE0810DD6DB224
69852DFD09072166B39A460A6445C0DD586CDECF1C20C8AE5BBEF7DD1B588D40
CCD2017F6BB4E3BBDDA26A7E3A59FF453E350A44BCB4CDD572EACEA8FA6484BB
8D6612AEBF3C6F47D29BE463542F5D9EAEC2771BF64E6370740E0D8DE75B1357
F8721671AF537D5D4040CB084EB4E2CC34D2466A0115AF84E1B0042895983A1D
06B89FB4CE6EA0486F3F3B823520AB82011A1D4B277227F8611560B1E7933FDC
BB3A792B344525BDA08839E151CE794B2F32C9B7A01FBAC9E01CC87EBCC7D1F6
CF0111C3A1E8AAC71A908749D44FBD9AD0DADECBD50ADA380339C32AC6913667
8DF9317CE0B12B4FF79E59B743F5BB3AF2D519FF27D9459CBF97222C15E6FC2A
0F91FC719B941525FAE59361CEB69CEBC2A8645912BAA8D1B6C1075EE3056A0C
10D25065CB03A442E0EC6E0E1698DB3B4C98A0BE3278E9649F1F9532E0D392DF
D3A0342B8971F21E1B0A74414BA3348CC5BE7120C37632D8DF359F8D9B992F2E
E60B6F470FE3F11DE54CDA541EDAD891CE6279CFCD3E7E6F1618B166FD2C1D05
848FD2C5F6FB2299F523F357A632762393A8353156CCCD02ACF081625A75EBB5
6E16369788D273CCDE96629281B949D04C50901B71C65614E6C6C7BD327A140A
45E1D006C3F27B9AC9AA53FD62A80F00BB25BFE235BDD2F671126905B2040222
B6CBCF7CCD769C2B53113EC01640E3D338ABBD602547ADF0BA38209CF746CE76
77AFA1C52075606085CBFE4E8AE88DD87AAAF9B04CF9AA7E1948C25C02FB8A8C
01C36AE4D6EBE1F990D4F869A65CDEA03F09252DC208E69FB74E6132CE77E25B
578FDFE33AC372E6
*/}.toString().slice(14,-3);

//work with that multiline string:
var pi_test_string = pi_test_string.split('\n').join('');			//remove new line '\r\n'
console.log('pi_test_string', pi_test_string);
console.log('pi_test_string.length', pi_test_string.length);
pi_test_string = '3.'+pi_test_string.toLowerCase();				//add '3.' and convert to lower case


//	BBP-algo for n-th digit:

	//	Original BBP-formula, to compute Pi, with any precission:
	//Pi = ( Infinity ) Sum ( k=0 ) [ 1/16^k * ( ( 4 / 8k+1 ) - ( 2 / 8k+4 ) - ( 1 / 8k+5 ) - ( 1 / 8k+6 ) ) ]

	//n-th decimal digit:
	//		pi = 3.14159265...
	//1-th dec-digit = pi * 10^1 = 31.4159265... % 10 (dec) = 1.4159265... -> floor (1.4159265...) = 1
	//2-th dec-digit = pi * 10^2 = 314.159265... % 10 (dec) = 4.159265.... -> floor (4.159265....) = 4
	//3-th dec-digit = pi * 10^3 = 3141.59265... % 10 (dec) = 1.59265..... -> floor (1.59265.....) = 1
	//4-th dec-digit = pi * 10^4 = 31415.9265... % 10 (dec) = 5.9265...... -> floor (5.9265......) = 5
	//5-th dec-digit = pi * 10^5 = 314159.265... % 10 (dec) = 9.265....... -> floor (9.265.......) = 9
	//6-th dec-digit = pi * 10^6 = 3141592.65... % 10 (dec) = 2.65........ -> floor (2.65........) = 2
	//7-th dec-digit = pi * 10^7 = 31415926.5... % 10 (dec) = 6.5......... -> floor (6.5.........) = 6
	//8-th dec-digit = pi * 10^8 = 314159265 ... % 10 (dec) = 5........... -> floor (5...........) = 5

	//	N-th decimal digit of Pi:
	//Pi = Floor ( ( ( Infinity ) Sum ( k=0 ) [ (10^N) * 1/16^k * ( ( 4 / 8k+1 ) - ( 2 / 8k+4 ) - ( 1 / 8k+5 ) - ( 1 / 8k+6 ) ) ] ) % 10 );

	//n-th hexadecimal digit:
	//		pi = 3.243f6a88...
	//1-th hex-digit = pi * 16^1 = 32.43f6a88... % 10 (hex) = 2.43f6a88... -> floor (2.43f6a88...) = 2
	//2-th hex-digit = pi * 16^2 = 324.3f6a88... % 10 (hex) = 4.3f6a88.... -> floor (4.3f6a88....) = 4
	//3-th hex-digit = pi * 16^3 = 3243.f6a88... % 10 (hex) = 3.f6a88..... -> floor (3.f6a88.....) = 3
	//4-th hex-digit = pi * 16^4 = 3243f.6a88... % 10 (hex) = f.6a88...... -> floor (f.6a88......) = f
	//5-th hex-digit = pi * 16^5 = 3243f6.a88... % 10 (hex) = 6.a88....... -> floor (6.a88.......) = 6
	//6-th hex-digit = pi * 16^6 = 3243f6a.88... % 10 (hex) = a.88........ -> floor (a.88........) = a
	//7-th hex-digit = pi * 16^7 = 3243f6a8.8... % 10 (hex) = 8.8......... -> floor (8.8.........) = 8
	//8-th hex-digit = pi * 16^8 = 3243f6a88.... % 10 (hex) = 8........... -> floor (8...........) = 8

	//	N-th hexadecimal digit of Pi:
	//Pi = Floor ( ( ( Infinity ) Sum ( k=0 ) [ (16^N) * 1/16^k * ( ( 4 / 8k+1 ) - ( 2 / 8k+4 ) - ( 1 / 8k+5 ) - ( 1 / 8k+6 ) ) ] ) % 10 );
	//Pi = Floor ( ( ( Infinity ) Sum ( k=0 ) [ (16^N/16^k) * ( ( 4 / 8k+1 ) - ( 2 / 8k+4 ) - ( 1 / 8k+5 ) - ( 1 / 8k+6 ) ) ] ) % 10 );
	//Pi = Floor ( ( ( Infinity ) Sum ( k=0 ) [ 16^(N-k) * ( ( 4 / 8k+1 ) - ( 2 / 8k+4 ) - ( 1 / 8k+5 ) - ( 1 / 8k+6 ) ) ] ) % 10 );
	//Pi = Floor ( ( ( Infinity ) Sum ( k=0 ) [ + ( ( 16^(N-k) * 4 ) / 8k+1 ) - ( ( 16^(N-k) * 2 ) / 8k+4 ) - ( (16^(N-k) * 1 ) / 8k+5 ) - ( ( 16^(N-k) * 1 )  / 8k+6 ) ] ) % 10 );

	//Pi = Floor 	(
	//					(
	//						+ 4 * ( Infinity ) Sum ( k=0 ) [ 16^(N-k) / 8k+1 ) ]
	//						- 2 * ( Infinity ) Sum ( k=0 ) [ 16^(N-k) / 8k+4 ) ]
	//						- 1 * ( Infinity ) Sum ( k=0 ) [ 16^(N-k) / 8k+5 ) ]
	//						- 1 * ( Infinity ) Sum ( k=0 ) [ 16^(N-k) / 8k+6 ) ]
	//					) % 16
	//				);

	//Because 16 = 2^4;
	//Pi = Floor 	(
	//					(
	//						+ 4 * ( Infinity ) Sum ( k=0 ) [ 2^(4N-4k) / 8k+1 ) ]
	//						- 2 * ( Infinity ) Sum ( k=0 ) [ 2^(4N-4k) / 8k+4 ) ]
	//						- 1 * ( Infinity ) Sum ( k=0 ) [ 2^(4N-4k) / 8k+5 ) ]
	//						- 1 * ( Infinity ) Sum ( k=0 ) [ 2^(4N-4k) / 8k+6 ) ]
	//					) % 16
	//				);
	//This allow binary exponentiation

	//	Split sums up to N
	//Pi = Floor 	(
	//					(
	//						+ 4 * ( ( n ) Sum ( k=0 ) [ 2^(4N-4k) / 8k+1 ) ] + ( Infinity ) Sum ( k=n+1 ) [ 2^(4N-4k) / 8k+1 ) ] )
	//						- 2 * ( ( n ) Sum ( k=0 ) [ 2^(4N-4k) / 8k+4 ) ] + ( Infinity ) Sum ( k=n+1 ) [ 2^(4N-4k) / 8k+4 ) ] )
	//						- 1 * ( ( n ) Sum ( k=0 ) [ 2^(4N-4k) / 8k+5 ) ] + ( Infinity ) Sum ( k=n+1 ) [ 2^(4N-4k) / 8k+5 ) ] )
	//						- 1 * ( ( n ) Sum ( k=0 ) [ 2^(4N-4k) / 8k+6 ) ] + ( Infinity ) Sum ( k=n+1 ) [ 2^(4N-4k) / 8k+6 ) ] )
	//					) % 16
	//				);

	//Because when k>n, right sums always give small numbers, and left sums give whole numbers,
	//		dropping of whole part, can be used with modpow, which is faster, than binary exponentiation;
	//Pi = Floor 	(
	//					(
	//						+ 4 * ( Infinity ) Sum ( k=0 ) [ 2^(4N-4k) mod (8k+1) / 8k+1 ) ] + ( Infinity ) Sum ( k=n+1 ) [ 2^(4N-4k) / 8k+1 ) ] )
	//						- 2 * ( Infinity ) Sum ( k=0 ) [ 2^(4N-4k) mod (8k+4) / 8k+4 ) ] + ( Infinity ) Sum ( k=n+1 ) [ 2^(4N-4k) / 8k+4 ) ] )
	//						- 1 * ( Infinity ) Sum ( k=0 ) [ 2^(4N-4k) mod (8k+5) / 8k+5 ) ] + ( Infinity ) Sum ( k=n+1 ) [ 2^(4N-4k) / 8k+5 ) ] )
	//						- 1 * ( Infinity ) Sum ( k=0 ) [ 2^(4N-4k) mod (8k+6) / 8k+6 ) ] + ( Infinity ) Sum ( k=n+1 ) [ 2^(4N-4k) / 8k+6 ) ] )
	//					) % 16
	//				);

	//Pi = Floor 	(
	//					(
	//						+ 4 * ( n ) Sum ( k=0 ) [ powmod( 2, (4N-4k), (8k+1)) / 8k+1 ) ] + ( Infinity ) Sum ( k=n+1 ) [ 2^(4N-4k) / 8k+1 ) ] )
	//						- 2 * ( n ) Sum ( k=0 ) [ powmod( 2, (4N-4k), (8k+1)) / 8k+4 ) ] + ( Infinity ) Sum ( k=n+1 ) [ 2^(4N-4k) / 8k+1 ) ] )
	//						- 1 * ( n ) Sum ( k=0 ) [ powmod( 2, (4N-4k), (8k+1)) / 8k+5 ) ] + ( Infinity ) Sum ( k=n+1 ) [ 2^(4N-4k) / 8k+1 ) ] )
	//						- 1 * ( n ) Sum ( k=0 ) [ powmod( 2, (4N-4k), (8k+1)) / 8k+6 ) ] + ( Infinity ) Sum ( k=n+1 ) [ 2^(4N-4k) / 8k+1 ) ] )
	//					) % 16
	//				);

	//		And after all, no need to compute pi up to infinity, with binary exponentiation.
	//		To get N-th digit, from pi, with precission up to N-th digit, just enough to compute left sums,
	//Pi = Floor 	(
	//					(
	//						+ 4 * ( n ) Sum ( k=0 ) [ powmod( 2, (4N-4k), (8k+1)) / 8k+1 ) ]
	//						- 2 * ( n ) Sum ( k=0 ) [ powmod( 2, (4N-4k), (8k+1)) / 8k+4 ) ]
	//						- 1 * ( n ) Sum ( k=0 ) [ powmod( 2, (4N-4k), (8k+1)) / 8k+5 ) ]
	//						- 1 * ( n ) Sum ( k=0 ) [ powmod( 2, (4N-4k), (8k+1)) / 8k+6 ) ]
	//					) % 16
	//				);
	//	Here is base = 2 only, and this is binary exponentiation, moreover fast modpow is using, and this is faster.

//fast modPow
function powmod( base, exp, mod ){
  if (exp == 0) return 1;
  if (exp % 2 == 0){
    return Math.pow( powmod( base, (exp / 2), mod), 2) % mod;
  }
  else {
    return (base * powmod( base, (exp - 1), mod)) % mod;
  }
}

/**
   Bailey-Borwein-Plouffe digit-extraction algorithm for pi
    <https://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula#BBP_digit-extraction_algorithm_for_.CF.80>
*/

//cache results:
var cachedHexDigitsOfPi = {};

function NthHexDigitOfPi(n, cache) {
	if(cachedHexDigitsOfPi.hasOwnProperty(n)){
		return cachedHexDigitsOfPi[n];
	}

    var partial = function(n, c) {
        var sum = 0;

        // Left sum
        var k;

		var iter = 0;
        for (k = 0; k <= n - 1; k++) {													//for each k, from 0 up to (n-1)
			iter++;

			//var add = (powmod(16, (n - 1 - k), (8 * k + c))) / (8 * k + c);			//add 					( ( 16^( n-1-k ) % ( 8k+c ) ) / ( 8k+c ) )
			var add = (powmod(2, (4 * n - 4 * 1 - 4 * k), (8 * k + c))) / (8 * k + c);	//16 = 2^4, so add 		( ( 2^( 4*n-4*1-4*k ) % ( 8k+c ) ) / ( 8k+c ) )
			sum += add;																	//add this to sum
        }

		/*
        // Right sum. This converges fast...
        var prev = undefined;
        for(k = n; sum !== prev; k++) {													//for each k
			iter++;

            prev = sum;
			var add = Math.pow( 16, ( n - 1 - k ) ) / ( 8 * k + c );
		//	console.log('add', add);
            sum += add;
        }
			//	This no need, and was been just commented, and return the same result,
			//		because for k from 0 up to (n-1), pi digits, already computed with precission up to n-th digit.
		*/
        return sum;
    };

    /**
        JavaScript's modulus operator gives the wrong
        result for negative numbers. E.g. `-2.9 % 1`
        returns -0.9, the correct result is 0.1.
    */
    var mod1 = function(x) {
        return x < 0 ? 1 - (-x % 1) : x % 1;
    };

    var s = 0;
    s +=  4 * partial(n, 1);	//+ ( 4 / 8k+1 )
    s += -2 * partial(n, 4);	//- ( 2 / 8k+4 )
    s += -1 * partial(n, 5);	//- ( 1 / 8k+5 )
    s += -1 * partial(n, 6);	//- ( 1 / 8k+6 )

    s = mod1(s);
    var NthHexDigit = Math.floor(s * 16).toString(16);
	cachedHexDigitsOfPi[n] = NthHexDigit;
	return NthHexDigit;
}
//Usage:
//console.log( '100501-th hex digit: ', NthHexDigitOfPi( 100501 ) );


console.log('wait computing...');

//	test all multistring, above:
/*
console.log('wait computing...');
var result = '3.';
for( dig = 1; dig <= 8336; dig++ ){
	result += NthHexDigitOfPi( dig );
}
console.log( result );
console.log( result == pi_test_string );
*/

//fast test - 100 hex-digits
var result = '3.';
for( dig = 1; dig <= 100; dig++ ){
	result += NthHexDigitOfPi( dig );
}
console.log('test first 100 hexadecimal digits:')
console.log( result , pi_test_string.slice(0, 102));
console.log( result === pi_test_string.slice(0, 102) );

console.log('8336-th digit of PI: ', NthHexDigitOfPi( 8336 ) );

//1 million-th hexadecimal digit:
console.log('Wait computing 1000000-th digit of PI...');

var num = 1000000;
var numthHexDigit;
console.log(num+'-th digit of PI: ', (numthHexDigit = NthHexDigitOfPi( num ), numthHexDigit) ); //set value and return
console.log('According this: https://www.pi2e.ch/blog/wp-content/uploads/2017/03/pi_hex_1m.txt 1000000-th hex digit is 2')
console.log('Is valid? ', (numthHexDigit === '2') );

//	In left-sum, there is "powmod(16, (nth - 1 - k), (8 * k + c))"
//	this depends from nth
//	so when nth changed, sequence of numbers is changed.
//	For N-th hex digit, algo working or N-th iterations of left-sum.
//	So, by other words, PI-value, is computed, in some form, every time, for each hex-digit.
//	Maybe previous steps of cycle, can be cached, or/and used to compute all previous digits, but I'm not sure in this.


// "PI with 9 lines of code". source: http://ajennings.net/blog/a-million-digits-of-pi-in-9-lines-of-javascript.html
var i = 1n; var rest = 20n; var digits = 1000n;
var x = 3n * (10n ** (rest + digits));
var pi = x;
while (x > 0) {
	x = x * i / ((i + 1n) * 4n);
	pi += x / (i + 2n);
	i += 2n;
}
console.log('Pi with '+ digits+' decimal points: \n', pi / (10n ** rest));
</script>
	Open this in new tab, and see console.log (F12 button);
	<script>
	//first 8336 hexadecimal digits of pi: https://gist.github.com/retrohacker/e5fff72b7b75ee058924

	//multiline string:
	var pi_test_string = function(){/*
	243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89
	452821E638D01377BE5466CF34E90C6CC0AC29B7C97C50DD3F84D5B5B5470917
	9216D5D98979FB1BD1310BA698DFB5AC2FFD72DBD01ADFB7B8E1AFED6A267E96
	BA7C9045F12C7F9924A19947B3916CF70801F2E2858EFC16636920D871574E69
	A458FEA3F4933D7E0D95748F728EB658718BCD5882154AEE7B54A41DC25A59B5
	9C30D5392AF26013C5D1B023286085F0CA417918B8DB38EF8E79DCB0603A180E
	6C9E0E8BB01E8A3ED71577C1BD314B2778AF2FDA55605C60E65525F3AA55AB94
	5748986263E8144055CA396A2AAB10B6B4CC5C341141E8CEA15486AF7C72E993
	B3EE1411636FBC2A2BA9C55D741831F6CE5C3E169B87931EAFD6BA336C24CF5C
	7A325381289586773B8F48986B4BB9AFC4BFE81B6628219361D809CCFB21A991
	487CAC605DEC8032EF845D5DE98575B1DC262302EB651B8823893E81D396ACC5
	0F6D6FF383F442392E0B4482A484200469C8F04A9E1F9B5E21C66842F6E96C9A
	670C9C61ABD388F06A51A0D2D8542F68960FA728AB5133A36EEF0B6C137A3BE4
	BA3BF0507EFB2A98A1F1651D39AF017666CA593E82430E888CEE8619456F9FB4
	7D84A5C33B8B5EBEE06F75D885C12073401A449F56C16AA64ED3AA62363F7706
	1BFEDF72429B023D37D0D724D00A1248DB0FEAD349F1C09B075372C980991B7B
	25D479D8F6E8DEF7E3FE501AB6794C3B976CE0BD04C006BAC1A94FB6409F60C4
	5E5C9EC2196A246368FB6FAF3E6C53B51339B2EB3B52EC6F6DFC511F9B30952C
	CC814544AF5EBD09BEE3D004DE334AFD660F2807192E4BB3C0CBA85745C8740F
	D20B5F39B9D3FBDB5579C0BD1A60320AD6A100C6402C7279679F25FEFB1FA3CC
	8EA5E9F8DB3222F83C7516DFFD616B152F501EC8AD0552AB323DB5FAFD238760
	53317B483E00DF829E5C57BBCA6F8CA01A87562EDF1769DBD542A8F6287EFFC3
	AC6732C68C4F5573695B27B0BBCA58C8E1FFA35DB8F011A010FA3D98FD2183B8
	4AFCB56C2DD1D35B9A53E479B6F84565D28E49BC4BFB9790E1DDF2DAA4CB7E33
	62FB1341CEE4C6E8EF20CADA36774C01D07E9EFE2BF11FB495DBDA4DAE909198
	EAAD8E716B93D5A0D08ED1D0AFC725E08E3C5B2F8E7594B78FF6E2FBF2122B64
	8888B812900DF01C4FAD5EA0688FC31CD1CFF191B3A8C1AD2F2F2218BE0E1777
	EA752DFE8B021FA1E5A0CC0FB56F74E818ACF3D6CE89E299B4A84FE0FD13E0B7
	7CC43B81D2ADA8D9165FA2668095770593CC7314211A1477E6AD206577B5FA86
	C75442F5FB9D35CFEBCDAF0C7B3E89A0D6411BD3AE1E7E4900250E2D2071B35E
	226800BB57B8E0AF2464369BF009B91E5563911D59DFA6AA78C14389D95A537F
	207D5BA202E5B9C5832603766295CFA911C819684E734A41B3472DCA7B14A94A
	1B5100529A532915D60F573FBC9BC6E42B60A47681E6740008BA6FB5571BE91F
	F296EC6B2A0DD915B6636521E7B9F9B6FF34052EC585566453B02D5DA99F8FA1
	08BA47996E85076A4B7A70E9B5B32944DB75092EC4192623AD6EA6B049A7DF7D
	9CEE60B88FEDB266ECAA8C71699A17FF5664526CC2B19EE1193602A575094C29
	A0591340E4183A3E3F54989A5B429D656B8FE4D699F73FD6A1D29C07EFE830F5
	4D2D38E6F0255DC14CDD20868470EB266382E9C6021ECC5E09686B3F3EBAEFC9
	3C9718146B6A70A1687F358452A0E286B79C5305AA5007373E07841C7FDEAE5C
	8E7D44EC5716F2B8B03ADA37F0500C0DF01C1F040200B3FFAE0CF51A3CB574B2
	25837A58DC0921BDD19113F97CA92FF69432477322F547013AE5E58137C2DADC
	C8B576349AF3DDA7A94461460FD0030EECC8C73EA4751E41E238CD993BEA0E2F
	3280BBA1183EB3314E548B384F6DB9086F420D03F60A04BF2CB8129024977C79
	5679B072BCAF89AFDE9A771FD9930810B38BAE12DCCF3F2E5512721F2E6B7124
	501ADDE69F84CD877A5847187408DA17BC9F9ABCE94B7D8CEC7AEC3ADB851DFA
	63094366C464C3D2EF1C18473215D908DD433B3724C2BA1612A14D432A65C451
	50940002133AE4DD71DFF89E10314E5581AC77D65F11199B043556F1D7A3C76B
	3C11183B5924A509F28FE6ED97F1FBFA9EBABF2C1E153C6E86E34570EAE96FB1
	860E5E0A5A3E2AB3771FE71C4E3D06FA2965DCB999E71D0F803E89D65266C825
	2E4CC9789C10B36AC6150EBA94E2EA78A5FC3C531E0A2DF4F2F74EA7361D2B3D
	1939260F19C279605223A708F71312B6EBADFE6EEAC31F66E3BC4595A67BC883
	B17F37D1018CFF28C332DDEFBE6C5AA56558218568AB9802EECEA50FDB2F953B
	2AEF7DAD5B6E2F841521B62829076170ECDD4775619F151013CCA830EB61BD96
	0334FE1EAA0363CFB5735C904C70A239D59E9E0BCBAADE14EECC86BC60622CA7
	9CAB5CABB2F3846E648B1EAF19BDF0CAA02369B9655ABB5040685A323C2AB4B3
	319EE9D5C021B8F79B540B19875FA09995F7997E623D7DA8F837889A97E32D77
	11ED935F166812810E358829C7E61FD696DEDFA17858BA9957F584A51B227263
	9B83C3FF1AC24696CDB30AEB532E30548FD948E46DBC312858EBF2EF34C6FFEA
	FE28ED61EE7C3C735D4A14D9E864B7E342105D14203E13E045EEE2B6A3AAABEA
	DB6C4F15FACB4FD0C742F442EF6ABBB5654F3B1D41CD2105D81E799E86854DC7
	E44B476A3D816250CF62A1F25B8D2646FC8883A0C1C7B6A37F1524C369CB7492
	47848A0B5692B285095BBF00AD19489D1462B17423820E0058428D2A0C55F5EA
	1DADF43E233F70613372F0928D937E41D65FECF16C223BDB7CDE3759CBEE7460
	4085F2A7CE77326EA607808419F8509EE8EFD85561D99735A969A7AAC50C06C2
	5A04ABFC800BCADC9E447A2EC3453484FDD567050E1E9EC9DB73DBD3105588CD
	675FDA79E3674340C5C43465713E38D83D28F89EF16DFF20153E21E78FB03D4A
	E6E39F2BDB83ADF7E93D5A68948140F7F64C261C94692934411520F77602D4F7
	BCF46B2ED4A20068D40824713320F46A43B7D4B7500061AF1E39F62E97244546
	14214F74BF8B88404D95FC1D96B591AF70F4DDD366A02F45BFBC09EC03BD9785
	7FAC6DD031CB850496EB27B355FD3941DA2547E6ABCA0A9A28507825530429F4
	0A2C86DAE9B66DFB68DC1462D7486900680EC0A427A18DEE4F3FFEA2E887AD8C
	B58CE0067AF4D6B6AACE1E7CD3375FECCE78A399406B2A4220FE9E35D9F385B9
	EE39D7AB3B124E8B1DC9FAF74B6D185626A36631EAE397B23A6EFA74DD5B4332
	6841E7F7CA7820FBFB0AF54ED8FEB397454056ACBA48952755533A3A20838D87
	FE6BA9B7D096954B55A867BCA1159A58CCA9296399E1DB33A62A4A563F3125F9
	5EF47E1C9029317CFDF8E80204272F7080BB155C05282CE395C11548E4C66D22
	48C1133FC70F86DC07F9C9EE41041F0F404779A45D886E17325F51EBD59BC0D1
	F2BCC18F41113564257B7834602A9C60DFF8E8A31F636C1B0E12B4C202E1329E
	AF664FD1CAD181156B2395E0333E92E13B240B62EEBEB92285B2A20EE6BA0D99
	DE720C8C2DA2F728D012784595B794FD647D0862E7CCF5F05449A36F877D48FA
	C39DFD27F33E8D1E0A476341992EFF743A6F6EABF4F8FD37A812DC60A1EBDDF8
	991BE14CDB6E6B0DC67B55106D672C372765D43BDCD0E804F1290DC7CC00FFA3
	B5390F92690FED0B667B9FFBCEDB7D9CA091CF0BD9155EA3BB132F88515BAD24
	7B9479BF763BD6EB37392EB3CC1159798026E297F42E312D6842ADA7C66A2B3B
	12754CCC782EF11C6A124237B79251E706A1BBE64BFB63501A6B101811CAEDFA
	3D25BDD8E2E1C3C9444216590A121386D90CEC6ED5ABEA2A64AF674EDA86A85F
	BEBFE98864E4C3FE9DBC8057F0F7C08660787BF86003604DD1FD8346F6381FB0
	7745AE04D736FCCC83426B33F01EAB71B08041873C005E5F77A057BEBDE8AE24
	55464299BF582E614E58F48FF2DDFDA2F474EF388789BDC25366F9C3C8B38E74
	B475F25546FCD9B97AEB26618B1DDF84846A0E79915F95E2466E598E20B45770
	8CD55591C902DE4CB90BACE1BB8205D011A862487574A99EB77F19B6E0A9DC09
	662D09A1C4324633E85A1F0209F0BE8C4A99A0251D6EFE101AB93D1D0BA5A4DF
	A186F20F2868F169DCB7DA83573906FEA1E2CE9B4FCD7F5250115E01A70683FA
	A002B5C40DE6D0279AF88C27773F8641C3604C0661A806B5F0177A28C0F586E0
	006058AA30DC7D6211E69ED72338EA6353C2DD94C2C21634BBCBEE5690BCB6DE
	EBFC7DA1CE591D766F05E4094B7C018839720A3D7C927C2486E3725F724D9DB9
	1AC15BB4D39EB8FCED54557808FCA5B5D83D7CD34DAD0FC41E50EF5EB161E6F8
	A28514D96C51133C6FD5C7E756E14EC4362ABFCEDDC6C837D79A323492638212
	670EFA8E406000E03A39CE37D3FAF5CFABC277375AC52D1B5CB0679E4FA33742
	D382274099BC9BBED5118E9DBF0F7315D62D1C7EC700C47BB78C1B6B21A19045
	B26EB1BE6A366EB45748AB2FBC946E79C6A376D26549C2C8530FF8EE468DDE7D
	D5730A1D4CD04DC62939BBDBA9BA4650AC9526E8BE5EE304A1FAD5F06A2D519A
	63EF8CE29A86EE22C089C2B843242EF6A51E03AA9CF2D0A483C061BA9BE96A4D
	8FE51550BA645BD62826A2F9A73A3AE14BA99586EF5562E9C72FEFD3F752F7DA
	3F046F6977FA0A5980E4A91587B086019B09E6AD3B3EE593E990FD5A9E34D797
	2CF0B7D9022B8B5196D5AC3A017DA67DD1CF3ED67C7D2D281F9F25CFADF2B89B
	5AD6B4725A88F54CE029AC71E019A5E647B0ACFDED93FA9BE8D3C48D283B57CC
	F8D5662979132E28785F0191ED756055F7960E44E3D35E8C15056DD488F46DBA
	03A161250564F0BDC3EB9E153C9057A297271AECA93A072A1B3F6D9B1E6321F5
	F59C66FB26DCF3197533D928B155FDF5035634828ABA3CBB28517711C20AD9F8
	ABCC5167CCAD925F4DE817513830DC8E379D58629320F991EA7A90C2FB3E7BCE
	5121CE64774FBE32A8B6E37EC3293D4648DE53696413E680A2AE0810DD6DB224
	69852DFD09072166B39A460A6445C0DD586CDECF1C20C8AE5BBEF7DD1B588D40
	CCD2017F6BB4E3BBDDA26A7E3A59FF453E350A44BCB4CDD572EACEA8FA6484BB
	8D6612AEBF3C6F47D29BE463542F5D9EAEC2771BF64E6370740E0D8DE75B1357
	F8721671AF537D5D4040CB084EB4E2CC34D2466A0115AF84E1B0042895983A1D
	06B89FB4CE6EA0486F3F3B823520AB82011A1D4B277227F8611560B1E7933FDC
	BB3A792B344525BDA08839E151CE794B2F32C9B7A01FBAC9E01CC87EBCC7D1F6
	CF0111C3A1E8AAC71A908749D44FBD9AD0DADECBD50ADA380339C32AC6913667
	8DF9317CE0B12B4FF79E59B743F5BB3AF2D519FF27D9459CBF97222C15E6FC2A
	0F91FC719B941525FAE59361CEB69CEBC2A8645912BAA8D1B6C1075EE3056A0C
	10D25065CB03A442E0EC6E0E1698DB3B4C98A0BE3278E9649F1F9532E0D392DF
	D3A0342B8971F21E1B0A74414BA3348CC5BE7120C37632D8DF359F8D9B992F2E
	E60B6F470FE3F11DE54CDA541EDAD891CE6279CFCD3E7E6F1618B166FD2C1D05
	848FD2C5F6FB2299F523F357A632762393A8353156CCCD02ACF081625A75EBB5
	6E16369788D273CCDE96629281B949D04C50901B71C65614E6C6C7BD327A140A
	45E1D006C3F27B9AC9AA53FD62A80F00BB25BFE235BDD2F671126905B2040222
	B6CBCF7CCD769C2B53113EC01640E3D338ABBD602547ADF0BA38209CF746CE76
	77AFA1C52075606085CBFE4E8AE88DD87AAAF9B04CF9AA7E1948C25C02FB8A8C
	01C36AE4D6EBE1F990D4F869A65CDEA03F09252DC208E69FB74E6132CE77E25B
	578FDFE33AC372E6
	*/}.toString().slice(14,-3);

	//work with that multiline string:
	var pi_test_string = pi_test_string.split('\n').join(''); //remove new line '\r\n'
	console.log('pi_test_string', pi_test_string);
	console.log('pi_test_string.length', pi_test_string.length);
	pi_test_string = '3.'+pi_test_string.toLowerCase(); //add '3.' and convert to lower case




	// BBP-algo for n-th digit:

	// Original BBP-formula, to compute Pi, with any precission:
	//Pi = ( Infinity ) Sum ( k=0 ) [ 1/16^k * ( ( 4 / 8k+1 ) - ( 2 / 8k+4 ) - ( 1 / 8k+5 ) - ( 1 / 8k+6 ) ) ]

	//n-th decimal digit:
	// pi = 3.14159265...
	//1-th dec-digit = pi * 10^1 = 31.4159265... % 10 (dec) = 1.4159265... -> floor (1.4159265...) = 1
	//2-th dec-digit = pi * 10^2 = 314.159265... % 10 (dec) = 4.159265.... -> floor (4.159265....) = 4
	//3-th dec-digit = pi * 10^3 = 3141.59265... % 10 (dec) = 1.59265..... -> floor (1.59265.....) = 1
	//4-th dec-digit = pi * 10^4 = 31415.9265... % 10 (dec) = 5.9265...... -> floor (5.9265......) = 5
	//5-th dec-digit = pi * 10^5 = 314159.265... % 10 (dec) = 9.265....... -> floor (9.265.......) = 9
	//6-th dec-digit = pi * 10^6 = 3141592.65... % 10 (dec) = 2.65........ -> floor (2.65........) = 2
	//7-th dec-digit = pi * 10^7 = 31415926.5... % 10 (dec) = 6.5......... -> floor (6.5.........) = 6
	//8-th dec-digit = pi * 10^8 = 314159265 ... % 10 (dec) = 5........... -> floor (5...........) = 5

	// N-th decimal digit of Pi:
	//Pi = Floor ( ( ( Infinity ) Sum ( k=0 ) [ (10^N) * 1/16^k * ( ( 4 / 8k+1 ) - ( 2 / 8k+4 ) - ( 1 / 8k+5 ) - ( 1 / 8k+6 ) ) ] ) % 10 );

	//n-th hexadecimal digit:
	// pi = 3.243f6a88...
	//1-th hex-digit = pi * 16^1 = 32.43f6a88... % 10 (hex) = 2.43f6a88... -> floor (2.43f6a88...) = 2
	//2-th hex-digit = pi * 16^2 = 324.3f6a88... % 10 (hex) = 4.3f6a88.... -> floor (4.3f6a88....) = 4
	//3-th hex-digit = pi * 16^3 = 3243.f6a88... % 10 (hex) = 3.f6a88..... -> floor (3.f6a88.....) = 3
	//4-th hex-digit = pi * 16^4 = 3243f.6a88... % 10 (hex) = f.6a88...... -> floor (f.6a88......) = f
	//5-th hex-digit = pi * 16^5 = 3243f6.a88... % 10 (hex) = 6.a88....... -> floor (6.a88.......) = 6
	//6-th hex-digit = pi * 16^6 = 3243f6a.88... % 10 (hex) = a.88........ -> floor (a.88........) = a
	//7-th hex-digit = pi * 16^7 = 3243f6a8.8... % 10 (hex) = 8.8......... -> floor (8.8.........) = 8
	//8-th hex-digit = pi * 16^8 = 3243f6a88.... % 10 (hex) = 8........... -> floor (8...........) = 8

	// N-th hexadecimal digit of Pi:
	//Pi = Floor ( ( ( Infinity ) Sum ( k=0 ) [ (16^N) * 1/16^k * ( ( 4 / 8k+1 ) - ( 2 / 8k+4 ) - ( 1 / 8k+5 ) - ( 1 / 8k+6 ) ) ] ) % 10 );
	//Pi = Floor ( ( ( Infinity ) Sum ( k=0 ) [ (16^N/16^k) * ( ( 4 / 8k+1 ) - ( 2 / 8k+4 ) - ( 1 / 8k+5 ) - ( 1 / 8k+6 ) ) ] ) % 10 );
	//Pi = Floor ( ( ( Infinity ) Sum ( k=0 ) [ 16^(N-k) * ( ( 4 / 8k+1 ) - ( 2 / 8k+4 ) - ( 1 / 8k+5 ) - ( 1 / 8k+6 ) ) ] ) % 10 );
	//Pi = Floor ( ( ( Infinity ) Sum ( k=0 ) [ + ( ( 16^(N-k) * 4 ) / 8k+1 ) - ( ( 16^(N-k) * 2 ) / 8k+4 ) - ( (16^(N-k) * 1 ) / 8k+5 ) - ( ( 16^(N-k) * 1 ) / 8k+6 ) ] ) % 10 );

	//Pi = Floor (
	// (
	// + 4 * ( Infinity ) Sum ( k=0 ) [ 16^(N-k) / 8k+1 ) ]
	// - 2 * ( Infinity ) Sum ( k=0 ) [ 16^(N-k) / 8k+4 ) ]
	// - 1 * ( Infinity ) Sum ( k=0 ) [ 16^(N-k) / 8k+5 ) ]
	// - 1 * ( Infinity ) Sum ( k=0 ) [ 16^(N-k) / 8k+6 ) ]
	// ) % 16
	// );

	//Because 16 = 2^4;
	//Pi = Floor (
	// (
	// + 4 * ( Infinity ) Sum ( k=0 ) [ 2^(4N-4k) / 8k+1 ) ]
	// - 2 * ( Infinity ) Sum ( k=0 ) [ 2^(4N-4k) / 8k+4 ) ]
	// - 1 * ( Infinity ) Sum ( k=0 ) [ 2^(4N-4k) / 8k+5 ) ]
	// - 1 * ( Infinity ) Sum ( k=0 ) [ 2^(4N-4k) / 8k+6 ) ]
	// ) % 16
	// );
	//This allow binary exponentiation

	// Split sums up to N
	//Pi = Floor (
	// (
	// + 4 * ( ( n ) Sum ( k=0 ) [ 2^(4N-4k) / 8k+1 ) ] + ( Infinity ) Sum ( k=n+1 ) [ 2^(4N-4k) / 8k+1 ) ] )
	// - 2 * ( ( n ) Sum ( k=0 ) [ 2^(4N-4k) / 8k+4 ) ] + ( Infinity ) Sum ( k=n+1 ) [ 2^(4N-4k) / 8k+4 ) ] )
	// - 1 * ( ( n ) Sum ( k=0 ) [ 2^(4N-4k) / 8k+5 ) ] + ( Infinity ) Sum ( k=n+1 ) [ 2^(4N-4k) / 8k+5 ) ] )
	// - 1 * ( ( n ) Sum ( k=0 ) [ 2^(4N-4k) / 8k+6 ) ] + ( Infinity ) Sum ( k=n+1 ) [ 2^(4N-4k) / 8k+6 ) ] )
	// ) % 16
	// );

	//Because when k>n, right sums always give small numbers, and left sums give whole numbers,
	// dropping of whole part, can be used with modpow, which is faster, than binary exponentiation;
	//Pi = Floor (
	// (
	// + 4 * ( Infinity ) Sum ( k=0 ) [ 2^(4N-4k) mod (8k+1) / 8k+1 ) ] + ( Infinity ) Sum ( k=n+1 ) [ 2^(4N-4k) / 8k+1 ) ] )
	// - 2 * ( Infinity ) Sum ( k=0 ) [ 2^(4N-4k) mod (8k+4) / 8k+4 ) ] + ( Infinity ) Sum ( k=n+1 ) [ 2^(4N-4k) / 8k+4 ) ] )
	// - 1 * ( Infinity ) Sum ( k=0 ) [ 2^(4N-4k) mod (8k+5) / 8k+5 ) ] + ( Infinity ) Sum ( k=n+1 ) [ 2^(4N-4k) / 8k+5 ) ] )
	// - 1 * ( Infinity ) Sum ( k=0 ) [ 2^(4N-4k) mod (8k+6) / 8k+6 ) ] + ( Infinity ) Sum ( k=n+1 ) [ 2^(4N-4k) / 8k+6 ) ] )
	// ) % 16
	// );

	//Pi = Floor (
	// (
	// + 4 * ( n ) Sum ( k=0 ) [ powmod( 2, (4N-4k), (8k+1)) / 8k+1 ) ] + ( Infinity ) Sum ( k=n+1 ) [ 2^(4N-4k) / 8k+1 ) ] )
	// - 2 * ( n ) Sum ( k=0 ) [ powmod( 2, (4N-4k), (8k+1)) / 8k+4 ) ] + ( Infinity ) Sum ( k=n+1 ) [ 2^(4N-4k) / 8k+1 ) ] )
	// - 1 * ( n ) Sum ( k=0 ) [ powmod( 2, (4N-4k), (8k+1)) / 8k+5 ) ] + ( Infinity ) Sum ( k=n+1 ) [ 2^(4N-4k) / 8k+1 ) ] )
	// - 1 * ( n ) Sum ( k=0 ) [ powmod( 2, (4N-4k), (8k+1)) / 8k+6 ) ] + ( Infinity ) Sum ( k=n+1 ) [ 2^(4N-4k) / 8k+1 ) ] )
	// ) % 16
	// );

	// And after all, no need to compute pi up to infinity, with binary exponentiation.
	// To get N-th digit, from pi, with precission up to N-th digit, just enough to compute left sums,
	//Pi = Floor (
	// (
	// + 4 * ( n ) Sum ( k=0 ) [ powmod( 2, (4N-4k), (8k+1)) / 8k+1 ) ]
	// - 2 * ( n ) Sum ( k=0 ) [ powmod( 2, (4N-4k), (8k+1)) / 8k+4 ) ]
	// - 1 * ( n ) Sum ( k=0 ) [ powmod( 2, (4N-4k), (8k+1)) / 8k+5 ) ]
	// - 1 * ( n ) Sum ( k=0 ) [ powmod( 2, (4N-4k), (8k+1)) / 8k+6 ) ]
	// ) % 16
	// );
	// Here is base = 2 only, and this is binary exponentiation, moreover fast modpow is using, and this is faster.

	//fast modPow
	function powmod( base, exp, mod ){
	if (exp == 0) return 1;
	if (exp % 2 == 0){
	return Math.pow( powmod( base, (exp / 2), mod), 2) % mod;
	}
	else {
	return (base * powmod( base, (exp - 1), mod)) % mod;
	}
	}

	/**
	Bailey-Borwein-Plouffe digit-extraction algorithm for pi
	<https://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula#BBP_digit-extraction_algorithm_for_.CF.80>
	*/

	//cache results:
	var cachedHexDigitsOfPi = {};

	function NthHexDigitOfPi(n, cache) {
	if(cachedHexDigitsOfPi.hasOwnProperty(n)){
	return cachedHexDigitsOfPi[n];
	}

	var partial = function(n, c) {
	var sum = 0;

	// Left sum
	var k;

	var iter = 0;
	for (k = 0; k <= n - 1; k++) { //for each k, from 0 up to (n-1)
	iter++;

	//var add = (powmod(16, (n - 1 - k), (8 * k + c))) / (8 * k + c); //add ( ( 16^( n-1-k ) % ( 8k+c ) ) / ( 8k+c ) )
	var add = (powmod(2, (4 * n - 4 * 1 - 4 * k), (8 * k + c))) / (8 * k + c); //16 = 2^4, so add ( ( 2^( 4n-41-4*k ) % ( 8k+c ) ) / ( 8k+c ) )
	sum += add; //add this to sum
	}

	/*
	// Right sum. This converges fast...
	var prev = undefined;
	for(k = n; sum !== prev; k++) { //for each k
	iter++;

	prev = sum;
	var add = Math.pow( 16, ( n - 1 - k ) ) / ( 8 * k + c );
	// console.log('add', add);
	sum += add;
	}
	// This no need, and was been just commented, and return the same result,
	// because for k from 0 up to (n-1), pi digits, already computed with precission up to n-th digit.
	*/
	return sum;
	};

	/**
	JavaScript's modulus operator gives the wrong
	result for negative numbers. E.g. `-2.9 % 1`
	returns -0.9, the correct result is 0.1.
	*/
	var mod1 = function(x) {
	return x < 0 ? 1 - (-x % 1) : x % 1;
	};

	var s = 0;
	s += 4 * partial(n, 1); //+ ( 4 / 8k+1 )
	s += -2 * partial(n, 4); //- ( 2 / 8k+4 )
	s += -1 * partial(n, 5); //- ( 1 / 8k+5 )
	s += -1 * partial(n, 6); //- ( 1 / 8k+6 )

	s = mod1(s);
	var NthHexDigit = Math.floor(s * 16).toString(16);
	cachedHexDigitsOfPi[n] = NthHexDigit;
	return NthHexDigit;
	}
	//Usage:
	//console.log( '100501-th hex digit: ', NthHexDigitOfPi( 100501 ) );


	console.log('wait computing...');

	// test all multistring, above:
	/*
	console.log('wait computing...');
	var result = '3.';
	for( dig = 1; dig <= 8336; dig++ ){
	result += NthHexDigitOfPi( dig );
	}
	console.log( result );
	console.log( result == pi_test_string );
	*/

	//fast test - 100 hex-digits
	var result = '3.';
	for( dig = 1; dig <= 100; dig++ ){
	result += NthHexDigitOfPi( dig );
	}
	console.log('test first 100 hexadecimal digits:')
	console.log( result , pi_test_string.slice(0, 102));
	console.log( result === pi_test_string.slice(0, 102) );

	console.log('8336-th digit of PI: ', NthHexDigitOfPi( 8336 ) );

	//1 million-th hexadecimal digit:
	console.log('Wait computing 1000000-th digit of PI...');

	var num = 1000000;
	var numthHexDigit;
	console.log(num+'-th digit of PI: ', (numthHexDigit = NthHexDigitOfPi( num ), numthHexDigit) ); //set value and return
	console.log('According this: https://www.pi2e.ch/blog/wp-content/uploads/2017/03/pi_hex_1m.txt 1000000-th hex digit is 2')
	console.log('Is valid? ', (numthHexDigit === '2') );

	// In left-sum, there is "powmod(16, (nth - 1 - k), (8 * k + c))"
	// this depends from nth
	// so when nth changed, sequence of numbers is changed.
	// For N-th hex digit, algo working or N-th iterations of left-sum.
	// So, by other words, PI-value, is computed, in some form, every time, for each hex-digit.
	// Maybe previous steps of cycle, can be cached, or/and used to compute all previous digits, but I'm not sure in this.


	// "PI with 9 lines of code". source: http://ajennings.net/blog/a-million-digits-of-pi-in-9-lines-of-javascript.html
	var i = 1n; var rest = 20n; var digits = 1000n;
	var x = 3n * (10n ** (rest + digits));
	var pi = x;
	while (x > 0) {
	x = x * i / ((i + 1n) * 4n);
	pi += x / (i + 2n);
	i += 2n;
	}
	console.log('Pi with '+ digits+' decimal points: \n', pi / (10n ** rest));
	</script>