[Tutor] Actual code that illustrates problem

[Danny Yoo]

> To try to find factors of z, using w.
>
>>>>
>
> * What are the inputs? What is 'z', and what is 'w'?
>
> ******
>
> z is the number to be factores.
>
> w is a "witness", a number that may help find the factors of z.

[My apologies in advance; this message is a bit long.]



Hi Kermit,

Ok, good.  You should add this as a comment to the function's header, so 
that other people can see this.  Here is an example:

def strongfac(z, w):
     """z is the number to be factored.
        w is a witness that may help find the factors of z.
     """
     ## rest of function body.

At the very beginning of the function body, we're allowed to make a string 
that acts as function documentation.  Python programmers expect this kind 
of "documentation string" at the head of a function, so that they're 
prepared for what comes next.



> * What are the outputs? What is the return value of strongfac?
>
> The output is the return value of strongfac.
> fac = [ x, y, difficulty of factoring z using w]
> or
> fac = [0,0,0] if strongfac could not factor z using w.

Great!  Ok, I'm assuming that 'x' and 'y' are two arbitrary factors of 
'z'.  Are there other properties about x and y that you want to state, 
such as: "x is always prime", or do we make no guarantees about this?



At this point, I'm distilling what you've said into a documentation 
string:

def strongfac(z, w):
     """strongfac: number number -> [x, y, difficulty]

     Factors z into two pieces, returning those two pieces as well as the
     difficulty in factoring z.  w is a witness that may help find the
     factors of z.

     If no factors can be found, returns [0, 0, 0].
     """
     ## rest of function body.


Does this make sense so far?  The point is to make it easy for humans to 
understand your program.




>> # face = [x,y,0]
> [some code cut]
>> # face[0] = x
>> # face[1] = y
>> # face[2] = 0
>
>> The three assignments to face[0] through face[2] don't do anything 
>> effective and clutter the code.
>
> In fact, I knew that.  I inserted it in an attempt to overide the 
> apparent bug that I saw.
>
> Sometimes it worked.

This is a bad sign.  It should not have worked.  *grin*

Next time you hit something mysterious like this, mention it to the list. 
It'll be a good puzzle for the others here to take a look at.  Your code 
should be as rational as possible.  Don't just add code in hoping that 
it'll fix some problem: try to understand why it's not working first. 
Look for root causes.




>> In fermat(), there are magic numbers:
> [cut]
>> These seem pretty arbitrary. Can you explain them?

> Yes.  These are limits of ranges.  I had not yet evolved the module to 
> replace the range limits with parameters.



About strongfac():

> Have you considered breaking those out as independent helper functions?
>
> I have considered it.

Consider it more strongly.  *grin*



Here, I'll help you get started.  strongfac() starts off looking something 
like this:

#################################################################
def strongfac(z,w):
     x = gcd(z,w-1)
     if x > 1:
         if x < z:
             y = z/x
             return [x,y,0]
     w2 = (w * w)%z
     s = ksqrt(w2)
     if w2 == s * s:
         if s != w:
             x = gcd(z,kabs(w2 - s))
             if x > 1:
                 if x < z:
                     return [x,y,0]
     ## other tests
################################################################

(I'm trimming out the print statements just to keep this small.)


Those two tests, the P-1 and square=square tests, can be broken out into 
two separate functions.  Let's see what this might look like:

############################################################
def check_p_minus_1(z, w):
     """Checks to see if z can be factored by the P-1 Method.
     If so, returns [x, y, 0]; otherwise, returns [0, 0, 0].
     """
     x = gcd(z,w-1)
     if x > 1:
         if x < z:
             y = z/x
             return [x,y,0]
     return [0, 0, 0]
############################################################

This "refactoring" allows us to look at check_p_minus_1's action in 
isolation, and also makes it easier to ask questions like: what happens if 
x > z?  Is it really possible that the return value from gcd() is bigger 
than the initial inputs to gcd()?  (As far as I understand gcd(), NO!)

So this refactoring is useful just as a matter of letting someone just 
look at a small bit of code and understand it completely.  As far as I can 
understand, check_p_minus_1() should work even if it's simplified to:

##########################
def check_p_minus_1(z, w):
     x = gcd(z, w-1)
     if x != 1:
         return [x, z/x, 0]
     return [0, 0, 0]
##########################




Anyway, once we break out the P-1 check out into a separate function, we 
can rewrite strongfac() to use check_p_minus_1():

################################
def strongfac(z, w):
     face = check_p_minus_1(z, w)
     if face != [0, 0, 0]:
         return face
     ## ... other tests here
################################


Can you try this?  Can you try breaking out the square=square test in a 
similar way to how I treated the check_p_minus_1() code?




The high level goal here is to turn strongfac() into a very simple looking 
function.  In pseudocode, it'll look something like:

############################
def strongfac(z, w):
     use check_p_minus_1 test and return if it succeeds
     use square=square test and return if it succeeds
     ...
############################

This will make strongfac very regular to read.  It'll also make it much 
easier to trace why one of your return values isn't returning what you 
want.