patternpythonMinor

Trial Multiplication for Factorization

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

trialforfactorizationmultiplication

Problem

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\$, lower \$p\$ while continuing where the last \$p\$ and the last \$q\$ left off.

#Trial Multiplication
TM0)  
    p_start 0)  
    q_start 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

    }

}

Solution

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 = 1L & 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 = 1L & 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)

Code Snippets

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)

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)

Context

StackExchange Code Review Q#83997, answer score: 2

Revisions (0)

No revisions yet.