Amazon.com Widgets Using Fermat's factoring algorithm for the reduce function -- seems to work fine
Welcome, Guest. Please login or register.
Did you miss your activation email?
September 01, 2014, 12:29:26 AM
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
| |-+ Objective-C Workshop Aug 11 - 13
| | |-+ Using Fermat's factoring algorithm for the reduce function -- seems to work fine
Pages: [1] Go Down
Print
Author Topic: Using Fermat's factoring algorithm for the reduce function -- seems to work fine (Read 16245 times)
aaanwar
Newbie
*
Posts: 1






on: August 12, 2009, 11:53:43 AM



// use this reduce function

-(void) reduce {
   NSMutableArray *numFactors = [[NSMutableArray alloc] init];
   NSMutableArray *denFactors = [[NSMutableArray alloc] init];
   
   factor( [self numerator], numFactors);
   factor( [self denomenator], denFactors);   
   
   while ([denFactors count] > 0 ) {
      NSNumber *factor=[denFactors objectAtIndex:([denFactors count]-1)];
      [denFactors removeLastObject];
      if ([numFactors containsObject: factor]) {
         [numFactors removeObject: factor];
         if ([self numerator] % [factor intValue] ==0 && [self denomenator] % [factor intValue] ==0) {
            [self setNumerator: [self numerator] / [factor intValue]];         
            [self setDenomenator: [self denomenator] / [factor intValue]];
         }
      }
   }
}

// now before this you need to add the utility function:

void factor(int num, NSMutableArray *result) {
   
   int pow2=1;
   int num2=num;
   while (num2 % 2==0) {
      num2/=2;
      pow2*=2;
      if (![result containsObject: [NSNumber numberWithInt: pow2]] ) {
         [result addObject: [NSNumber numberWithInt: pow2]];
         [result sortUsingSelector:@selector(compare:)];
      }
   }
   num=num2;
   
   if (num ==1) {
      [result addObject: [NSNumber numberWithInt: 1]];
      [result sortUsingSelector:@selector(compare:)];
   } else {
      int a = ceil(sqrt(num));
      float b2 = a*a - num;
      while ( floor(sqrt(b2))*floor(sqrt(b2)) != b2) {
         a+=1;
         b2=a*a -num;
      }
      int f=(int) (a - sqrt(b2));
      
      if (f!=1) {
         if (![result containsObject: [NSNumber numberWithInt: f]]) {
            [result addObject: [NSNumber numberWithInt: f]];
            [result sortUsingSelector:@selector(compare:)];
         }         
         factor(f, result);
         if (((int)floor(num/f))==((int)num/f)) {
            factor(num/f, result);
            if (![result containsObject: [NSNumber numberWithInt: num/f]]) {
               [result addObject: [NSNumber numberWithInt: num/f]];
               [result sortUsingSelector:@selector(compare:)];
            }         
         }
      }
   }
}
Logged
skochan
Administrator
Hero Member
*****
Posts: 3114







Reply #1 on: August 12, 2009, 07:12:36 PM

Wow!  That's a lot of code :-).  Thanks for sharing.

Cheers,

Steve Kochan
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.