Amazon.com Widgets Ex 6-7 Further speed enhancement
Welcome, Guest. Please login or register.
Did you miss your activation email?
April 18, 2014, 06:47:42 PM
Home Help Search chat Login Register 
News: Read this please.The Great Kangaroo Escape Looking for reviews of the 4th ed on Amazon!   Twitter:  @skochan
                     

+ Official Forum for Programming in Objective-C (the iPhone Programming Language) - Stephen Kochan
|-+ Old Stuff
| |-+ Chapter Study
| | |-+ Chapter 6 - Making Decisions
| | | |-+ Ex 6-7 Further speed enhancement
Pages: [1] Go Down
Print
Author Topic: Ex 6-7 Further speed enhancement (Read 1061 times)
dennishenley
Newbie
*
Posts: 12






on: September 27, 2011, 10:48:13 AM

In addition to the 2 ways to improved the program as stated in the exercise, I added a third way to speed things up.

I started thinking about the range of numbers. There's no need to test all the numbers up to 1 less than p. I think you only have to test up to p / 2.

Look at it this way. Using an even number like 104, divide it by 2. The result is 52. There cannot be any higher dividend because we are already at the lowest and the highest. So I changed the loop condition to only test the numbers from 2 to p/2.

Here's the code:

Code: (Objective-C)
//Program to generate a table of prime numbers 

#import <Foundation/Foundation.h>

int main (int argc, char *argv[])
{
    NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];
   
    int p, d, isPrime;

    p = 2;
    NSLog(@"%i", p++);
         
    for ( p = 3; p <= 49; p+=2 )
    {
        isPrime = 1;
        for ( d = 2; d < p/2; ++d )
            if ( p % d == 0 )
            {
                isPrime = 0;
                break;
            }
        if ( isPrime != 0 )
            NSLog (@"%i ", p);
    }
    [pool drain];
    return 0;
}
Logged
obrieti
Newbie
*
Posts: 3


Email




Reply #1 on: October 07, 2011, 11:09:01 PM

Tell me if I'm wrong, but I disagree with this.  We are not trying to find the greatest dividend, we are looking for the greatest prime in a set of numbers up to 50.  If you never allow the program to loop above p/2 (or 25 in this example) , you will miss 29, 37, 37, 41, 43, and 47  right?

I simply added a check for p > 2 and p % 2 == 0 immediately after setting isPrime in the initial for loop.

Then I added the isPrime == 1 in the condition statement of the 2nd for loop.

Logged
dennishenley
Newbie
*
Posts: 12






Reply #2 on: October 08, 2011, 10:54:06 AM

When I run the program I get all the Primes I expect (unto 47).

The reason I only test only half of the possible factors is due to symmetry.

Look at the factors for 16.

1 x 16
2 x 8
4 x 4
8 x 2
16 x 1

I can stop at 8 because the values will only repeat. There's probably a formula for figuring out how far to test, but that might take more computing power than just stoping at 1/2 the value. If you are testing thousands of numbers, this might be a savings.
Logged
obrieti
Newbie
*
Posts: 3


Email




Reply #3 on: October 08, 2011, 11:57:15 AM

You're absolutely right.... I was up late doing this last night, and initially completely agreed with your logic.  Then later, I got a little sleepy and 'lost the big picture'.  Agreed this is a nice touch thanks.
Logged
timjver
Newbie
*
Posts: 5


Email




Reply #4 on: February 21, 2012, 09:59:44 AM

You're right testing up until p - 1 makes no sense, but so doesn't testing up until p / 2. Testing wether p is divisible by p / 2 will never be necessary because the program would already have seen p is divisible by 2 and would not check all the way up to 52.

The smallest divisor of p, is the square root of p or lower. This is the case, because of p would be divisible by any number bigger than the square root of p, it would also be divisible by a number smaller than the square root of p. So, instead of this:
Code: (Objective-C)
for ( d = 2; d < p/2; ++d ) 
You can use this:
Code: (Objective-C)
for ( d = 2; d <= sqrt(p); ++d ) 
Now, things are speeded up even more.  Smiley
Logged
Pages: [1] Go Up
Print
Jump to:



Login with username, password and session length

Powered by MySQL Powered by PHP Powered by SMF 1.1.11 | SMF © 2006-2009, Simple Machines LLC Valid XHTML 1.0! Valid CSS!
Entire forum contents (c) 2009 classroomM.com. All rights reserved.