mersenneforum.org Power 2
 Register FAQ Search Today's Posts Mark Forums Read

2011-07-07, 14:36   #34
Gammatester

Mar 2009

2×19 Posts

Quote:
 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.

2011-07-07, 14:37   #35
R.D. Silverman

Nov 2003

11101001001002 Posts

Quote:
 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....

2011-07-07, 15:25   #36
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

6,379 Posts

Quote:
 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.

Last fiddled with by fivemack on 2011-07-07 at 15:25

2011-07-07, 15:38   #37
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 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.

2011-07-07, 15:41   #38
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 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.

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

2011-07-07, 16:11   #39
JohnFullspeed

May 2011
France

7×23 Posts

Quote:
 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)

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

 2011-07-07, 23:22 #40 Christenson     Dec 2010 Monticello 5×359 Posts 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.
2011-07-08, 06:05   #41
JohnFullspeed

May 2011
France

7·23 Posts
Power 2

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

Quote:
 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

2011-07-09, 15:13   #42
Christenson

Dec 2010
Monticello

5×359 Posts

Quote:
 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.

 2011-07-09, 19:39 #43 JohnFullspeed   May 2011 France 7·23 Posts Error 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
 2011-07-10, 15:54 #44 Christenson     Dec 2010 Monticello 5·359 Posts 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post petrw1 Teams 10 2019-10-15 17:36 CRGreathouse Hardware 9 2016-02-06 18:46 petrw1 Lounge 19 2013-12-13 13:00 JohnFullspeed Programming 5 2011-08-30 16:28 Unregistered Information & Answers 7 2008-08-30 14:36

All times are UTC. The time now is 01:09.

Sat Jan 23 01:09:16 UTC 2021 up 50 days, 21:20, 0 users, load averages: 2.18, 2.08, 2.08