Loading ...
Sorry, an error occurred while loading the content.

Re: [PrimeNumbers] Re: Boolean algebra solver?

Expand Messages
  • Justin
    Hi Ron, R Justin asked me for a real life example of how this technique R can be used to find factors, so at the risk of boring everyone R else, I thought
    Message 1 of 13 , Jun 4, 2004
    • 0 Attachment
      Hi Ron,

      R> Justin asked me for a real life example of how this technique
      R> can be used to find factors, so at the risk of boring everyone
      R> else, I thought I'd post it here on the forum. Here is a sample
      R> Maple code snippet ('#' begins a comment) that illustrates the
      R> problem:

      Thanks Ron. I think I've finally understood the idea of the technique. I
      also understand long-hand multiplication at long last ;)

      R> n:= [0,0,1,1,1,1]: # factor binary 001111 = decimal 15 = 3*5

      R> eqn := {a1+b1 = 1,
      R> a2+a1*b1+b2+c1 = 1,
      R> a2*b1+a1*b2+c2 = 1,
      R> a2*b2+c3+c4 = 0,
      R> c5 = 0};

      As you know, these equations in the Z(2) field are equivalent to boolean
      expressions. So they can be transformed the following way to eliminate the
      equality:

      lhs == 1 -> lhs
      lhs == 0 -> NOT(lhs) -> lhs+1 (equivalent to NOT using only xor)

      now all the ex-equations can be combined to one with AND (ie multiplication
      in Z(2)) to form one expression:

      (a1+b1) (a2+a1*b1+b2+c1) (a2*b1+a1*b2+c2) (a2*b2+c3+c4+1) (c5+1)

      This can be reduced algebraically and transformed to boolean:

      (a1 && b2 && ! a2 && ! b1) || (a2 && b1 && ! a1 && ! b2)

      Which in effect is indeed your solution:

      R> # But the solution is:

      R> a2:=0: a1:=1: # a0:=1, so that a= "011" binary = 3 decimal
      R> b2:=1: b1:=0: # a0:=1, so that b= "101" binary = 5 decimal

      R> # Where a=3 and b=5 are the factors of 15.


      I use Mathematica, and am not familiar with Maple, but I suppose it is
      just as capable of these transformations.

      I'm not sure about the practicability though. It already took a few seconds
      to reduce your example expressions (albeit with somewhat straightforward
      and probably not really efficient reduction algorithm).

      But then, what do I know? ;P

      --
      Justin
      ICQ 37456745
      AIM jasticle
    Your message has been successfully submitted and would be delivered to recipients shortly.