Power 2

[Gammatester]

Originally Posted by R.D. Silverman

Yes, but my method avoids checking all of the other limbs. There
could be a lot of them. The cost tradeoff is that computing a log
(even just a single one) is relatively expensive.

Since ldesnogu assumes a power of two base, I cannot see how you can be faster with your log_2 approach. If the most significant limb has a popcount > 1 both algorithms will have the result "No power of two". For popcount=1 you have to switch to "to another method". Either I am missing something obvious, or you have to include another limb in your log_2 calculation. If this limb is non-zero, ldesnogu terminates with "No power of two" and you get a better log_2 approximation. If the limb is zero, both algorithms have to continue.

IMO ldesnogu cannot be slower than you.

[R.D. Silverman]

Originally Posted by fivemack

Your method requires checking all (OK, some) of the other limbs if the log of the first limb (which will surely be computed by finding the first set bit, dividing by 2^that, then fitting some bit of power series) is close to a power of two; his method requires checking all (OK, some) of the other limbs if the first limb has only one set bit.

I am reasonably confident that computing a log is more expensive than checking for one set bit.

I agree with the last sentiment....!

I am not computing just the log of the first limb. I suggest computing
an approximation to the log of the entire number.

If R is the radix, then let N = sum A_i R^i i=0,M be a representation.

Compute an approximation to the log of A_M R^M, and not just an
approximation to log(A_M) by itself. log(R) can be precomputed.
Only if M*log(R) + log(A_M) is close to an int do the other limbs need
to be checked....

[fivemack]

Originally Posted by R.D. Silverman

I agree with the last sentiment....!

I am not computing just the log of the first limb. I suggest computing
an approximation to the log of the entire number.

If R is the radix, then let N = sum A_i R^i i=0,M be a representation.

Compute an approximation to the log of A_M R^M, and not just an
approximation to log(A_M) by itself.

I can see that that's sensible if you have a non-power-of-two radix. But everyone is assuming a power-of-two radix in this thread.

If you don't have a power-of-two radix then you can't use the bit-twiddling methods at all; and if you do have a power-of-two radix then adding a large multiple of log(2) to something that you're wanting to check for being a multiple of log(2) isn't obviously an efficient way to proceed.

[R.D. Silverman]

Originally Posted by fivemack

I can see that that's sensible if you have a non-power-of-two radix. But everyone is assuming a power-of-two radix in this thread.

If you don't have a power-of-two radix then you can't use the bit-twiddling methods at all; and if you do have a power-of-two radix then adding a large multiple of log(2) to something that you're wanting to check for being a multiple of log(2) isn't obviously an efficient way to proceed.

We agree.

[R.D. Silverman]

Originally Posted by Gammatester

Since ldesnogu assumes a power of two base, I cannot see how you can be faster with your log_2 approach. If the most significant limb has a popcount > 1 both algorithms will have the result "No power of two". For popcount=1 you have to switch to "to another method". Either I am missing something obvious, or you have to include another limb in your log_2 calculation. If this limb is non-zero, ldesnogu terminates with "No power of two" and you get a better log_2 approximation. If the limb is zero, both algorithms have to continue.

IMO ldesnogu cannot be slower than you.

See my follow on. The answer depends on the representation.

For a radix that is a power of 2, you are entirely correct. logs will
be slower.

[JohnFullspeed]

Originally Posted by R.D. Silverman

Sure. I'll do you this favor. But only in return for a favor on your part.
Stop all of your posting until you can supply some evidence that you have
studied some computational number theory.

I leave the mathematics for intelligent men like you

You must learn modesty when you don't know orenot understand you say it.
I don't know math so I ask when I need. It is thn Principe oaf education you learn when you will b and adult. no one except you find errors in my code
There is only you to say that? But you never says where I make error

For the power of 2 you don't explain us where my method was badyou only says that I
I am bad. (Most significant bit= Less significant bit The value have 1 bit and LSB (not LSD) have the exact power)

Sorry you don't understand hat you knows some thing that i do't know like Fermat factorization(thank to jasonp for is answer) but I also knows somethings that you don't know and perhaps useful for you



I NEVER SAYS THAT I KNOW THE MATHS
PERHAPS YOU UNDERSTAND THAT THE COMPUTER HAVE NOT THE HUMAN LOGIC BUT A LOGIC teach BY HUMAN. YOU WILL UNDERSTAND WHY THE Karatsuba
MULTIPLICATION IS BAD FOR THE COMPUTER YO MAKE A STEP IMPORTANT OR WHY A SHIT DIVISIOIN IS NOT ALWAYS GOOD

I wait your explication but I begin to know you You censure my tread to when,you dont have to answer

Whereis the Chirtenson mail where he say tthat I can code more 20 lins.e Censurde also (Moderation is not censure)

please answer to
1 why my method for thr power2 is bad?
2 why Karatsuba is bad for computer?
3 Why the mul by 3 in TSis bad ?

John

[Christenson]

Hi John:
It is not that your method for the power of 2 won't work, it's that the amount of time the instructions you propose takes varies widely depending on exactly which intel CPU you are on. There are slightly faster methods.

[JohnFullspeed]

It's better to say why the solution id less better than other
which say

you say something grossly wrong.

On a Intel 8 cycles for MSB and 8 LSB+ 4 for the cmp
In the solution
ons cycle for the sob 1 for 1 the and ,4 for the comp
No problem it's faster but like I say if you want to knnow thr power
my method give it.

It 's better than a search n a list.
John

[Christenson]

Originally Posted by JohnFullspeed

It's better to say why the solution id less better than other
which say


On a Intel 8 cycles for MSB and 8 LSB+ 4 for the cmp
In the solution
ons cycle for the sob 1 for 1 the and ,4 for the comp
No problem it's faster but like I say if you want to knnow thr power
my method give it.

It 's better than a search n a list.
John

People did say why the BSF/BSR method would be worse than asking if n &(n-1) was zero.
http://mersenneforum.org/showpost.ph...5&postcount=20

There's also a context issue -- if you have enough memory in L1 cache, you can simply create a logarithm table for one byte, and index by the byte into it to get either an error (not an even power of 2) or the logarithm base 2.

A lot of this depends on how frequently you actually get an even power of two; you want the most common case to be fastest.

All of these will be faster than a naive search of a list, as you say.

[JohnFullspeed]

I say BSL not BSF so no problem if n= or -1 BL reteur or 31

BSL Bit sighifiant left
BSR Bit signifiant rigth

BSL-BSR

BFR a,R
Bsl a,R1
Sub R1,R1,R3
RTN R3

n-&(n-1)

MOVA,R
MOV A,R1
Sub R1,1,R3
AND R1,R2,R3
RTN R3

It ' snear

[Christenson]

The way this is handled in a code like P95 is that tests are run at run-time to decide which alternative is fastest, then the fastest alternative is run.

Thus, if you think BSL/BSR might be best on some machines, the program runs a little test of BSL/BSR on realistic data and gets the timing. Then the program runs the subtracting 1 method against the same data, and gets the timing. My table lookup method might also be fastest, so the program tests that, too. One of them will be fastest, so that is the one that you use for the majority of the work.

Lavalamp has assured us that the people making chessplaying codes get very different results with BSL/BSR depending on which CPU is used.