Styjun

BritRail England Passes compared to return ticket for travel in England

Why didn't Doctor Strange restore Tony Stark after he used the Stones?

How long were the Apollo astronauts allowed to breathe 100% oxygen at 1 atmosphere continuously?

literal `0` beeing a valid candidate for int and const string& overloads causes ambiguous call

What is a Romeo Word™?

In this iconic lunar orbit rendezvous photo of John Houbolt, why do arrows #5 and #6 point the "wrong" way?

Pauli exclusion principle - black holes

What could make large expeditions ineffective for exploring territory full of dangers and valuable resources?

Is it legal for a supermarket to refuse to sell an adult beer if an adult with them doesn’t have their ID?

Why can't I hear fret buzz through the amp?

Proof that every field is perfect???

How important are the Author's mood and feelings for writing a story?

Is it possible to have a career in SciComp without contributing to arms research?

When designing an adventure, how can I ensure a continuous player experience in a setting that's likely to favor TPKs?

How can I automate this tensor computation?

Why are there few or no black super GMs?

Which GPUs to get for Mathematical Optimization (if any)?

Why did my "seldom" get corrected?

Do Australia and New Zealand have a travel ban on Somalis (like Wikipedia says)?

Should I have one hand on the throttle during engine ignition?

Could a US citizen born through "birth tourism" become President?

Changing iteration variable in Do loop

How to tell if JDK is available from within running JVM?

Should I have shared a document with a former employee?

Optimized integer logarithm base2 for BigInt

What is JavaScript's highest integer value that a number can go to without losing precision?Plot logarithmic axes with matplotlib in pythonLogarithmic sliderHow to sort an array of integers correctlyConvert a string to an integer in JavaScript?How do I check that a number is float or integer?Integer division with remainder in JavaScript?How can I get Google's Closure Compiler to eliminate attributesbigInt to base2How to obtain the amount of bits of a BigInt?

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;

3

1

This is the naive algorithm that calculates integer log2(n),

 function ilog2(n) // n is a positive non-zero BigInt
 const C1 = BigInt(1)
 const C2 = BigInt(2)
 for(var count=0; n>C1; count++) n = n/C2
 return count
 // example ilog2(16n)==4

I am testing optimizations (see example below) but they are not "for log2", as commented here.

There are something better using WebAssembly?

PS: if it is not possible a generic solution, to solve my problem I can use functions like ilog2_64bits(n), with WebAssembly truncating or ignoring some bits of input BigInt.

---

non-WebAssembly

Example of not so optimized in pure Javascript (ideal is WebAssembly!)... Trying adaptation of integerLogarithm() of BigInteger.js:

 function ilog2_pe(value, base=2n) 
 // example: ilog2_pe(255n) returns p: 128n, e: 7n 
 if (base <= value) 
 let i = ilog2_pe(value, base**2n);
 let t = i.p*base
 return (t <= value)
 ? p: t, e: i.e*2n + 1n 
 : p: i.p, e: i.e*2n 
 
 return p: 1n, e: 0n ;
 

 function ilog2_str(n) // 2*faster!
 return n.toString(2).length - 1
 

PS: it is running in modern browsers and last versions of NodeJS.

---

About performance... ilog2_pe(x64bits) is 4 times faster tham the naive ilog2(), ilog2_pe(x1024bits) is ~9 times faster... Was expected... But:

Any non-WebAssembly solution has so ugly performance, even for 512, 1024, 2048 bits... counting string digits with ilog_str() is 2 times faster!
For less tham 64 bits is 3 or more times faster.

javascript logarithm

share|improve this question

edited Mar 26 at 23:01

Peter Krauss

asked Mar 26 at 10:43

Peter KraussPeter Krauss

5,8861111 gold badges8888 silver badges191191 bronze badges

add a comment | 

3

1

This is the naive algorithm that calculates integer log2(n),

 function ilog2(n) // n is a positive non-zero BigInt
 const C1 = BigInt(1)
 const C2 = BigInt(2)
 for(var count=0; n>C1; count++) n = n/C2
 return count
 // example ilog2(16n)==4

I am testing optimizations (see example below) but they are not "for log2", as commented here.

There are something better using WebAssembly?

PS: if it is not possible a generic solution, to solve my problem I can use functions like ilog2_64bits(n), with WebAssembly truncating or ignoring some bits of input BigInt.

---

non-WebAssembly

Example of not so optimized in pure Javascript (ideal is WebAssembly!)... Trying adaptation of integerLogarithm() of BigInteger.js:

 function ilog2_pe(value, base=2n) 
 // example: ilog2_pe(255n) returns p: 128n, e: 7n 
 if (base <= value) 
 let i = ilog2_pe(value, base**2n);
 let t = i.p*base
 return (t <= value)
 ? p: t, e: i.e*2n + 1n 
 : p: i.p, e: i.e*2n 
 
 return p: 1n, e: 0n ;
 

 function ilog2_str(n) // 2*faster!
 return n.toString(2).length - 1
 

PS: it is running in modern browsers and last versions of NodeJS.

---

About performance... ilog2_pe(x64bits) is 4 times faster tham the naive ilog2(), ilog2_pe(x1024bits) is ~9 times faster... Was expected... But:

Any non-WebAssembly solution has so ugly performance, even for 512, 1024, 2048 bits... counting string digits with ilog_str() is 2 times faster!
For less tham 64 bits is 3 or more times faster.

javascript logarithm

share|improve this question

edited Mar 26 at 23:01

Peter Krauss

asked Mar 26 at 10:43

Peter KraussPeter Krauss

5,8861111 gold badges8888 silver badges191191 bronze badges

add a comment | 

This is the naive algorithm that calculates integer log2(n),

 function ilog2(n) // n is a positive non-zero BigInt
 const C1 = BigInt(1)
 const C2 = BigInt(2)
 for(var count=0; n>C1; count++) n = n/C2
 return count
 // example ilog2(16n)==4

I am testing optimizations (see example below) but they are not "for log2", as commented here.

There are something better using WebAssembly?

PS: if it is not possible a generic solution, to solve my problem I can use functions like ilog2_64bits(n), with WebAssembly truncating or ignoring some bits of input BigInt.

---

non-WebAssembly

Example of not so optimized in pure Javascript (ideal is WebAssembly!)... Trying adaptation of integerLogarithm() of BigInteger.js:

 function ilog2_pe(value, base=2n) 
 // example: ilog2_pe(255n) returns p: 128n, e: 7n 
 if (base <= value) 
 let i = ilog2_pe(value, base**2n);
 let t = i.p*base
 return (t <= value)
 ? p: t, e: i.e*2n + 1n 
 : p: i.p, e: i.e*2n 
 
 return p: 1n, e: 0n ;
 

 function ilog2_str(n) // 2*faster!
 return n.toString(2).length - 1
 

PS: it is running in modern browsers and last versions of NodeJS.

---

About performance... ilog2_pe(x64bits) is 4 times faster tham the naive ilog2(), ilog2_pe(x1024bits) is ~9 times faster... Was expected... But:

Any non-WebAssembly solution has so ugly performance, even for 512, 1024, 2048 bits... counting string digits with ilog_str() is 2 times faster!
For less tham 64 bits is 3 or more times faster.

javascript logarithm

share|improve this question

edited Mar 26 at 23:01

Peter Krauss

asked Mar 26 at 10:43

Peter KraussPeter Krauss

5,8861111 gold badges8888 silver badges191191 bronze badges

 function ilog2(n) // n is a positive non-zero BigInt
 const C1 = BigInt(1)
 const C2 = BigInt(2)
 for(var count=0; n>C1; count++) n = n/C2
 return count
 // example ilog2(16n)==4

 function ilog2_pe(value, base=2n) 
 // example: ilog2_pe(255n) returns p: 128n, e: 7n 
 if (base <= value) 
 let i = ilog2_pe(value, base**2n);
 let t = i.p*base
 return (t <= value)
 ? p: t, e: i.e*2n + 1n 
 : p: i.p, e: i.e*2n 
 
 return p: 1n, e: 0n ;
 

 function ilog2_str(n) // 2*faster!
 return n.toString(2).length - 1
 

share|improve this question

edited Mar 26 at 23:01

Peter Krauss

asked Mar 26 at 10:43

Peter KraussPeter Krauss

5,8861111 gold badges8888 silver badges191191 bronze badges

share|improve this question

edited Mar 26 at 23:01

Peter Krauss

asked Mar 26 at 10:43

Peter KraussPeter Krauss

5,8861111 gold badges8888 silver badges191191 bronze badges

asked Mar 26 at 10:43

Peter KraussPeter Krauss

5,8861111 gold badges8888 silver badges191191 bronze badges

asked Mar 26 at 10:43

Peter KraussPeter Krauss

5,8861111 gold badges8888 silver badges191191 bronze badges