mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2011-07-07, 14:36   #34
Gammatester
 
Gammatester's Avatar
 
Mar 2009

2×19 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
Gammatester is offline   Reply With Quote
Old 2011-07-07, 14:37   #35
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

Quote:
Originally Posted by fivemack View Post
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....
R.D. Silverman is offline   Reply With Quote
Old 2011-07-07, 15:25   #36
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

6,379 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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
fivemack is offline   Reply With Quote
Old 2011-07-07, 15:38   #37
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by fivemack View Post
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 is offline   Reply With Quote
Old 2011-07-07, 15:41   #38
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by Gammatester View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2011-07-07, 16:11   #39
JohnFullspeed
 
May 2011
France

7×23 Posts
Default helpme:I m so bad

Quote:
Originally Posted by R.D. Silverman View Post
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






JohnFullspeed is offline   Reply With Quote
Old 2011-07-07, 23:22   #40
Christenson
 
Christenson's Avatar
 
Dec 2010
Monticello

5×359 Posts
Default

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.
Christenson is offline   Reply With Quote
Old 2011-07-08, 06:05   #41
JohnFullspeed
 
May 2011
France

7·23 Posts
Default 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
JohnFullspeed is offline   Reply With Quote
Old 2011-07-09, 15:13   #42
Christenson
 
Christenson's Avatar
 
Dec 2010
Monticello

5×359 Posts
Default

Quote:
Originally Posted by JohnFullspeed View Post
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.
Christenson is offline   Reply With Quote
Old 2011-07-09, 19:39   #43
JohnFullspeed
 
May 2011
France

7·23 Posts
Default 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
JohnFullspeed is offline   Reply With Quote
Old 2011-07-10, 15:54   #44
Christenson
 
Christenson's Avatar
 
Dec 2010
Monticello

5·359 Posts
Default

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.
Christenson is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
More Power!!!! petrw1 Teams 10 2019-10-15 17:36
TDP as power used? CRGreathouse Hardware 9 2016-02-06 18:46
How much power am I really using? petrw1 Lounge 19 2013-12-13 13:00
Power??? JohnFullspeed Programming 5 2011-08-30 16:28
IBM Power 6 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.