3
\$\begingroup\$

I am trying a trial multiplication for factorization. This is a general example, but each sequence can be specified to pairs of sequences \${p,q}\$ for a given \$n\$. For example, if \$n\$ ended in 3, then {\$p,q\$} would be: {1,3},{3,1},{7,9} and {9,7} with sequence steps of -10 and 10 respectively.

The essence of the method is if \$pq < n\$, raise \$q\$. If \$pq > n\$, lower \$p\$ while continuing where the last \$p\$ and the last \$q\$ left off.

#Trial Multiplication
TM<- function (number){

    if (floor(sqrt(number))%%2==0)
    p_start <<- floor(sqrt(number))-1

    if (floor(sqrt(number))%%2>0)  
    p_start <<- floor(sqrt(number))

    if (ceiling(sqrt(number))%%2==0)
    q_start <<- ceiling(sqrt(number))+1

    if (ceiling(sqrt(number))%%2>0)  
    q_start <<- ceiling(sqrt(number)) 



    for (p in seq(p_start,1,-1)){   
      for (q in seq(q_start,number,1)){    

      #Quick primality tests for p and q... 
      #if(p%%3==0 | p%%5==0 | p%%7==0 | p%%11==0 | p%%13==0 | p%%17==0 | p%%19==0) break
      #if(q%%3==0 | q%%5==0 | q%%7==0 | q%%11==0 | q%%13==0 | q%%17==0 | q%%19==0) next 


      if(p*q==number)
      return(c(p,q)) 

      if(p*q>number) break


      q_start<<- q
      p_start<<- p

      }


  #if(q%%3==0 | q%%5==0 | q%%7==0 | q%%11==0 | q%%13==0 | q%%17==0 | q%%19==0) break
  #if(p%%3==0 | p%%5==0 | p%%7==0 | p%%11==0 | p%%13==0 | p%%17==0 | p%%19==0) next 


  if(p*q==number)
  return(c(p,q))  

  if(p*q<number) break

  p_start<<- p
  q_start<<- q

    }

}
\$\endgroup\$
10
  • \$\begingroup\$ Can you give more details or examples about how the algorithm is supposed to work? Or maybe a link to the methodology. The example you gave is hard to understand. Also, I'm not sure I understand the use of (q%%3==0 | q%%5==0 | q%%7==0 | q%%11==0 | q%%13==0 | q%%17==0 | q%%19==0). Most numbers are indeed divisible by the few first prime numbers so the double loop will essentially skip all the time. Testing your function with sample numbers, it either dies or returns nothing (i.e. keeps skiping the double loop)... \$\endgroup\$
    – flodel
    Mar 15, 2015 at 16:20
  • \$\begingroup\$ I have not run into an instance of the function dying or returning nothing. Ideally, it would only multiply the primes within the sequences. However, using just the identified sequences of 1's, 3's, 7's and 9's is more efficient than 6k+- 1. Unfortunately it is slow (hence the posting here for possible efficiency enhancements), and you can add a print command within the q loop to demonstrate the operations. I have notes on this and another method available here: (scribd.com/doc/245859553/…) \$\endgroup\$
    – Fred Viole
    Mar 15, 2015 at 16:31
  • \$\begingroup\$ Start a new session. Paste the code you wrote above. Then try TM(7) (fails) and TM(10) or TM(1234) (they return nothing). \$\endgroup\$
    – flodel
    Mar 15, 2015 at 16:43
  • \$\begingroup\$ I see your point for small numbers. Eliminating the quick primality tests and decreasing the steps to -1 and 1 for p and q respectively will work for those instances. Try TM(1927) which should return the factors and then try TM(1051) which returns nothing and is prime. Adding print(c(p,q)) after the break in the q loop will show the operations. \$\endgroup\$
    – Fred Viole
    Mar 15, 2015 at 16:57
  • \$\begingroup\$ Ok, so TM(1927) works... But if you try for (i in 1900:2000) print(TM(i)), you will see that only four numbers in that range return something... What does it say about the algorithm? Is the methodology wrong or just the implementation? 2000 looks like a simple number to work with (= 2^4 * 5^3): what should the algorithm return and can you walk us through the steps? \$\endgroup\$
    – flodel
    Mar 15, 2015 at 17:23

1 Answer 1

2
\$\begingroup\$

What is slow is to create seq(q_start,number,1). Take the example where number is 298,716,239: you are asking R to create a vector of nearly 300 million integers. It chokes. Instead of looping over sequences created in memory, it is easier to just keep the current value, increment and limit in memory. See for example:

TM <- function (n) {

   n <- as.integer(n)
   r <- sqrt(n)
   p <- as.integer(floor(r))
   q <- as.integer(ceiling(r))

   while (p >= 1L & q <= n) {
      if (p * q == n) return(c(p, q)) 
      if (p * q > n) { p <- p - 1L } else { q <- q + 1L } 
   }
   stop("hmm... we should not be here...")
}

TM(1900)
TM(298716239)

Now that's a start... If you try with a large prime, e.g. 298716247, it will take a very long time to converge towards 1 * 298716247 though. So you will have to get more creative to make it converge faster. At least, you should be fixed about why your original code was so slow.


Edit: here is an idea I got for making it converge faster where you update both p and q at each iteration. I hope the math checks out and I did not leave a corner case:

TM2 <- function (n){

   n <- as.integer(n) # everything is faster with integers
   r <- sqrt(n)
   p <- as.integer(floor(r))
   q <- as.integer(ceiling(r))
   while (p >= 1L & q <= n) {
      if (p * q == n) return(c(p, q)) 
      if (p*q > n) {
         p <- p - 1L
         q <- as.integer(floor(n / p))
      } else {
         q <- q + 1L
         p <- as.integer(ceiling(n / q))
      } 
   }
   stop("hmm...")
}

TM2(1900)
TM2(298716239)
TM2(298716247)
\$\endgroup\$
1
  • \$\begingroup\$ This is a lot faster and I am clear on why my original code was so slow, thank you @flodel. The creative aspect for faster convergence I had in mind is to run paired lists {1,9} etc. with a -10L and +10L in parallel with the 3 remaining paired lists {3,3},{7,7} and {9,1} (for this example of 298,716,239). \$\endgroup\$
    – Fred Viole
    Mar 16, 2015 at 3:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.