Re: [SLUG] c++... a bit OT
>void swap (int x, int y) { int tmp; tmp=x; x=y; y=tmp }
This isn't even correct. C passes arguments by value.
>#define swap(a,b) { a^=b;b^=a;a^=b }
>
>The second is from the book 'Applied Cryptography', which has some very
>tight code in it. It avoids the funtion call altogether, it doesn't
>create any tempory variables, and should become 3 XOR commands in total
>once compiled.
Except that a good compiler can probably beat the hell out of XOR
futzing if you define swap as an inline function.
Get it right, then make it fast.
--
SLUG - Sydney Linux User Group Mailing List - http://slug.org.au/
More Info: http://slug.org.au/lists/listinfo/slug
Re: [SLUG] c++... a bit OT
Rick Welykochy <[EMAIL PROTECTED]> wrote:
> On Wed, 15 Nov 2000, Doug Stalker wrote:
>> void swap (int x, int y) { int tmp; tmp=x; x=y; y=tmp }
>>
>> #define swap(a,b) { a^=b;b^=a;a^=b }
> But we are talking C++ here:
> inline void swapper(int& x, int& y) { x^=y; y^=x; x^=y; }
> Using C++ as a better C, we have the best of both
> of the above C solutions: 3 XORs only, and safe function calling.
inline is part of C99.
--
Debian GNU/Linux 2.2 is out! ( http://www.debian.org/ )
Email: Herbert Xu ~{PmV>HI~} <[EMAIL PROTECTED]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
--
SLUG - Sydney Linux User Group Mailing List - http://slug.org.au/
More Info: http://slug.org.au/lists/listinfo/slug
Re: [SLUG] c++... a bit OT
> "James" == James Wilkinson <[EMAIL PROTECTED]> writes:
James> This one time, at band camp, Alex Salmon said:
>> what do u mean by that exactly 3 to sqrt(x) by 2... what is x
James> if (num % 2 == 1) {
James> for (i = 3; i <= sqrt(num); i+=2) {
James> test;
James> }
James> }
You only actually have to test against the primes you've already
found.
So if you store them in an array, you can do something like this:
const int nprimes = 1;
uint64_t primes[nprimes] = {1, 2, 3, 5, 7, 11,};
int lastprimeIdx = 5;
bool_t isPrime(uint64_t num)
{
for (int i = 2; i <= lastprimeIdx; i++)
if (num % primes[i] == 0)
return false;
primes[++lastprimeIdx] = num;
return true;
}
int main()
{
uint64_t maybePrime;
for (maybePrime = primes[lastprimeIdx];
lastprimeIdx < nprimes; maybePrime += 2)
isPrime(maybePrime) && cout << maybePrime << "\n";
return 0;
}
--
SLUG - Sydney Linux User Group Mailing List - http://slug.org.au/
More Info: http://slug.org.au/lists/listinfo/slug
Re: [SLUG] c++... a bit OT
On Wed, 15 Nov 2000, Doug Stalker wrote:
> void swap (int x, int y) { int tmp; tmp=x; x=y; y=tmp }
>
> #define swap(a,b) { a^=b;b^=a;a^=b }
But we are talking C++ here:
inline void swapper(int& x, int& y) { x^=y; y^=x; x^=y; }
Using C++ as a better C, we have the best of both
of the above C solutions: 3 XORs only, and safe function calling.
Remember: #defines are evil & dangerous.
Try this on for size: swap(x++,--y)
At best it will give you bizarre compile time errors.
At worst it will compile and give you crap.
Whereas swapper(x++,--y) will warn you that the compiler
is taking a reference to a (discarded) temporary variable
(a towrst) or disallow taking a reference to an expression
(at best).
For a real twister, try this: swap(c,i) where c is char and i is int.
It will compile and trash some of the bits in i. Whereas C++
says "no way: cannot pass a char via an int reference".
--
Rick Welykochy || Praxis Services
"Tired of being a crash test dummy for Microsoft? Try Linux"
--
SLUG - Sydney Linux User Group Mailing List - http://slug.org.au/
More Info: http://slug.org.au/lists/listinfo/slug
Re: [SLUG] c++... a bit OT
>
> I was thinking, that as computers are binary machines, you could
> probably speed up your algorithm by thinking in binary rather than
> decimal. This will mean doing a lot of modification to your algorithm.
> Just thinking out loud again.
Even better would be to think it terms of how many opcodes it takes to
get the job done. Compare:
void swap (int x, int y) { int tmp; tmp=x; x=y; y=tmp }
#define swap(a,b) { a^=b;b^=a;a^=b }
The second is from the book 'Applied Cryptography', which has some very
tight code in it. It avoids the funtion call altogether, it doesn't
create any tempory variables, and should become 3 XOR commands in total
once compiled.
- Doug
--
_
Network Operations Engineer - Big Pond Advance Satellite
Ericsson Australia - Level 5, 184 The Broadway, Sydney 2000
Ph: +61-416-085-390 Email: [EMAIL PROTECTED]
--
SLUG - Sydney Linux User Group Mailing List - http://slug.org.au/
More Info: http://slug.org.au/lists/listinfo/slug
Re: [SLUG] c++... a bit OT
This one time, at band camp, Alex Salmon said:
>what do u mean by that exactly 3 to sqrt(x) by 2... what is x
if (num % 2 == 1) {
for (i = 3; i <= sqrt(num); i+=2) {
test;
}
}
He means, check for oddness, then go from 3 to the square root of the
number you're checking, in steps of 2.
>my idea was that as all primes end in 1,3,7,9 (not all ending 1 3 7 9 are
>primes tho)
Yeah, I stand corrected on that. feh, logic. I'm still playing with
kernel-package on Debian, and logic doesn't seem to apply here.
>James said somthing about doing everything in binary. what would be the
>actually outcome of this i mean how could i extract the last digit and set
>it to a int to test it as such??
I was thinking, that as computers are binary machines, you could
probably speed up your algorithm by thinking in binary rather than
decimal. This will mean doing a lot of modification to your algorithm.
Just thinking out loud again.
--
Sure, I subscribe to USENET, but I only get it for the articles.
(o_ '
//\
v_/_
--
SLUG - Sydney Linux User Group Mailing List - http://slug.org.au/
More Info: http://slug.org.au/lists/listinfo/slug
Re: [SLUG] c++... a bit OT
Alex Salmon wrote:
>
> my idea was that as all primes end in 1,3,7,9 (not all ending 1 3 7 9 are
> primes tho) so i wouldent need to start testing the number if it ended in
> say 5. sure this would slow down the working initily but as i get in to
> the say the 5 or more it would dramticly reduce time in the long
> run.. i hope ;-)
Checking for divisible by 5 won't help much
Assume an algorith like
isprime (int X)
{
for i = 2 to squareroot(X) (2 and odd numbers only)
if X modulus i ==0 return false
return true;
}
Then numbers ending in 5 (10% of the smaple space) get picked up in 3
tests if not pre-filtered. Filtering for divisible by five adds an
extra step to all checks.
Adding a filter for even numbers helps a lot though, as it avoid the
system having to set the for loop up just to exit on the first
iteration.
On my system, checking the first million numbers :
No prefiltering: 11 seconds
Prefilter for Even: 6 seconds
Prefilter for ending in 5s as well: 6 seconds
My test code:
(spoiler space for anyone who wants to do it themselves)
/
// Poor quality random number checker
// returns true if the test number is prime, false otherwise.
bool isprime (int testnum)
{
int i;
if ((testnum & 1) == 0) return false; //number is even
int nSqrt = (int)sqrt(testnum); //(do only once to avoid calling sqrt
every cycle of the for statement
// Test odd numbers from 3 to square root of testnum
for (i=3; i< nSqrt;i+=2)
{
if (testnum % i == 0) return false;
}
return true;
}
--
_
Network Operations Engineer - Big Pond Advance Satellite
Ericsson Australia - Level 5, 184 The Broadway, Sydney 2000
Ph: +61-416-085-390 Email: [EMAIL PROTECTED]
--
SLUG - Sydney Linux User Group Mailing List - http://slug.org.au/
More Info: http://slug.org.au/lists/listinfo/slug
Re: [SLUG] c++... a bit OT
hi what do u mean by that exactly 3 to sqrt(x) by 2... what is x i basicly get say the number what ever it is.. i originaly did say the num was 10 i did 10 % 9 then 10%8 then 10%7 etc if the answer to all of them (except 1 of course) is 0 then i add it to the list i then as u say div 2 before hand to see. my idea was that as all primes end in 1,3,7,9 (not all ending 1 3 7 9 are primes tho) so i wouldent need to start testing the number if it ended in say 5. sure this would slow down the working initily but as i get in to the say the 5 or more it would dramticly reduce time in the long run.. i hope ;-) James said somthing about doing everything in binary. what would be the actually outcome of this i mean how could i extract the last digit and set it to a int to test it as such?? thanks alex On Tue, 14 Nov 2000, Jon Carnes wrote: > Dude, your thinking in terms of decimal... > > Test for div by 2, then use the sqrt to limit your testing: 3 to sqrt(x) by > 2 > > -- SLUG - Sydney Linux User Group Mailing List - http://slug.org.au/ More Info: http://slug.org.au/lists/listinfo/slug
Re: [SLUG] c++... a bit OT
On Wed, Nov 15, 2000 at 01:28:48PM +1100, [EMAIL PROTECTED] wrote: > all primes end in either 1 3 7 or 9 except 2 and 5 > so it is pointless to test it if it dosent ie ends in a 5, so how can i > test to see if the last number is 1 3 7 9 before i start the curnum % x > !=0 9 = 3*3. It isn't prime You could first try mod-ing it against some of the more common ones, like 2, 3, 5, before going into your loop. That'll knock out everything ending in 2, 4, 6, 8 and 9. Forgive me if this sounds blatantly wrong, I'm not too familiar with the technique you're using. This is a linux list. You'd be alot better off looking at c++ groups on Usenet, or you should find a couple of relevant mailing lists on http://www.liszt.com/ While we're at it, can anybody suggest a good C mailing list? They seem to be fairly thin on the ground. Cheers, Peter -- SLUG - Sydney Linux User Group Mailing List - http://slug.org.au/ More Info: http://slug.org.au/lists/listinfo/slug
Re: [SLUG] c++... a bit OT
On Wed, 15 Nov 2000 [EMAIL PROTECTED] wrote: > i have played with a few things and am going well but im stumped with a > problem.. > > i decided to make a prime number generator. I started with > plain brute force trying every combo and it all worked well. found the sieve: http://forum.swarthmore.edu/dr.math/problems/schmidt4.1.96.html -- Rick Welykochy || Praxis Services "Tired of being a crash test dummy for Microsoft? Try Linux" -- SLUG - Sydney Linux User Group Mailing List - http://slug.org.au/ More Info: http://slug.org.au/lists/listinfo/slug
Re: [SLUG] c++... a bit OT
James Wilkinson wrote: > Well, you could convert it to a string, and look at the last character. > I think you're going to spend more time in the conversion than you think > you'd save by using it. Yeah, that'd work. > Another way, is to do your computations in binary, then you can mask off > the last couple of bits. i.e.: 1, 2, 3, 5, 7, 9, B, C, F are prime, you > can get the last 8 bits of an int by doing something like last8 = num & > 0xF This wont work because the higher bits can also contribute to the last digit of the decimal equivalent. Matthew -- SLUG - Sydney Linux User Group Mailing List - http://slug.org.au/ More Info: http://slug.org.au/lists/listinfo/slug
Re: [SLUG] c++... a bit OT
On Wed, Nov 15, 2000 at 11:37:18AM +1100, James Wilkinson wrote: > This one time, at band camp, [EMAIL PROTECTED] said: > > >all primes end in either 1 3 7 or 9 except 2 and 5 > > How about 39? That's not prime :) You need a better heuristic ;) No, he didn't say everything ending in 1 3 7 or 9 _is_ prime, just that to be prime you have to end in 1 3 7 or 9 (except 2 and 5) > > > so it is pointless to test it if it dosent ie ends in a 5, so how can i > >test to see if the last number is 1 3 7 9 before i start the curnum % x > >!=0 > > Well, you could convert it to a string, and look at the last character. > I think you're going to spend more time in the conversion than you think > you'd save by using it. number % 10 will give you the last digit. There are much better methods of finding prime numbers, though. sci.crypt has a lot of info about them. Stephen -- Stephen Norris[EMAIL PROTECTED] Farrow Norris Pty Ltd +61 2 417 243 239 PGP signature
Re: [SLUG] c++... a bit OT
On Wed, 15 Nov 2000, James Wilkinson wrote: > This one time, at band camp, [EMAIL PROTECTED] said: > > >all primes end in either 1 3 7 or 9 except 2 and 5 > > How about 39? That's not prime :) You need a better heuristic ;) he said all primes end in either 1 3 7 or 9, not that all numbers ending in 1 3 7 or 9 are prime -- Damien -- SLUG - Sydney Linux User Group Mailing List - http://slug.org.au/ More Info: http://slug.org.au/lists/listinfo/slug
Re: [SLUG] c++... a bit OT
[EMAIL PROTECTED] wrote: > i was wondering if someone could give me a hand on how to test the last > number ie. Try this: For all the bits in the number, add together the last digit of the decimal value that that bit represents. Do this again with the resulting number until you have a value < 10. That's your last digit. Example: 128 64 32 16 8 4 2 1 --- 0 1 1 1 0 1 0 1 == 117 Add 4 + 2 + 6 + 4 + 1 == 17 0 0 0 1 0 0 0 1 == 17 Add 6 + 1 == 7 Hey presto, you've got your number. Of course, you'll have to test whether that's really faster than doing a plain old 'x % 10'. Matthew -- SLUG - Sydney Linux User Group Mailing List - http://slug.org.au/ More Info: http://slug.org.au/lists/listinfo/slug
Re: [SLUG] c++... a bit OT
On Wed, 15 Nov 2000 [EMAIL PROTECTED] wrote:
> hi all
> i took the commen advice and i am teaching myself c++ ;-)
This is quite off topic ... but ...
> i have played with a few things and am going well but im stumped with a
> problem..
>
> i decided to make a prime number generator. I started with
> plain brute force trying every combo and it all worked well.
try a search on google for "the sieve of erastothenes" or somtehing
like that ... it is the classic algorithm for finding primes.
brute force will get you nowhere ;^)
why C++ would help you with a problem like this is beyond me :)
O-O integer perhaps? if (number(9).isprime()) { dothis();) } ???
--
Rick Welykochy || Praxis Services
"Tired of being a crash test dummy for Microsoft? Try Linux"
--
SLUG - Sydney Linux User Group Mailing List - http://slug.org.au/
More Info: http://slug.org.au/lists/listinfo/slug
Re: [SLUG] c++... a bit OT
This one time, at band camp, [EMAIL PROTECTED] said: >all primes end in either 1 3 7 or 9 except 2 and 5 How about 39? That's not prime :) You need a better heuristic ;) > so it is pointless to test it if it dosent ie ends in a 5, so how can i >test to see if the last number is 1 3 7 9 before i start the curnum % x >!=0 Well, you could convert it to a string, and look at the last character. I think you're going to spend more time in the conversion than you think you'd save by using it. Another way, is to do your computations in binary, then you can mask off the last couple of bits. i.e.: 1, 2, 3, 5, 7, 9, B, C, F are prime, you can get the last 8 bits of an int by doing something like last8 = num & 0xF -- Sure, I subscribe to USENET, but I only get it for the articles. (o_ ' //\ v_/_ -- SLUG - Sydney Linux User Group Mailing List - http://slug.org.au/ More Info: http://slug.org.au/lists/listinfo/slug
[SLUG] c++... a bit OT
hi all i took the commen advice and i am teaching myself c++ ;-) i have played with a few things and am going well but im stumped with a problem.. i decided to make a prime number generator. I started with plain brute force trying every combo and it all worked well. i was wondering if someone could give me a hand on how to test the last number ie. all primes end in either 1 3 7 or 9 except 2 and 5 so it is pointless to test it if it dosent ie ends in a 5, so how can i test to see if the last number is 1 3 7 9 before i start the curnum % x !=0 hope it is understanderble i just have a shocking migraine thanks alex -- SLUG - Sydney Linux User Group Mailing List - http://slug.org.au/ More Info: http://slug.org.au/lists/listinfo/slug
