Multiplicación de prueba para factorización -- algorithm campo con r camp codereview Relacionados El problema

Trial Multiplication for Factorization


3
vote

problema

Español

Estoy probando una multiplicación de prueba para factorización. Este es un ejemplo general, pero cada secuencia se puede especificar a pares de secuencias $ {P, Q} $ por un hecho $ n $. Por ejemplo, si $ N $ terminó en 3, entonces { $ P, Q $} sería: {1,3}, {3,1}, {7,9} y {9,7} con Pasos de secuencia de -10 y 10 respectivamente.

La esencia del método es si $ PQ & LT; n $, criar $ q $. $ PQ & GT; n $, menor $ P $ Mientras continúa donde el último $ P $ y el último $ Q $ se queda fuera.

  ksize5  
Original en ingles

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      }  } 
     
         
         

Lista de respuestas

2
 
vote

Lo que es lento es crear calcTwoK()1 . Tome el ejemplo donde 99887766555443312 es 298,716,239: le está pidiendo a R que cree un vector de casi 300 millones de enteros. Se ahoga. En lugar de hacer un bucle sobre secuencias creadas en la memoria, es más fácil mantener el valor actual, el incremento y el límite en la memoria. VER POR EJEMPLO:

  calcTwoK()3  

Ahora es un comienzo ... Si lo intentas con un gran primo, por ejemplo. calcTwoK()4 , tardará mucho tiempo en converger hacia calcTwoK()5 . Así que tendrás que ser más creativo para que converja más rápido. Al menos, debe ser arreglado sobre por qué su código original fue tan lento.


Editar: Aquí hay una idea que obtuve para hacer que converja más rápido donde actualice ambos 99887766555443316 y calcTwoK()7 en cada iteración. Espero que las matemáticas se comprueban y no deje una caja de la esquina:

  calcTwoK()8  
 

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) 
 
 
 
 

Relacionados problema

0  Text2VEC - Fit_Transform, $ Transform TF-IDF  ( Text2vec fit transform transform tf idf ) 
Lo siento si este es un lugar equivocado para publicar una pregunta. Tengo dos preguntas: ~ A) Estoy tratando de hacer similitud de texto utilizando la simi...

4  Vectorizamos la prueba exacta de Fisher  ( Vectorize fishers exact test ) 
Tengo dos marcos de datos / listas de datos, humanSplit 9988776655544331 , y son del formulario > ratSplit$Kidney_F_GSM1328570 ratGene ratRepli...

2  Invertir una función a través de una búsqueda  ( Invert a function via a lookup ) 
El objetivo de esta función es invertir una función de impuesto a la renta. Es decir, dado el impuesto pagado y el año financiero, la función debe devolver el...

4  Reducción del uso de la memoria para FIZZBUZZZ IN R  ( Reducing memory usage for fizzbuzz in r ) 
He estado intentando toda la noche para que mi Fuzzbuzz use por debajo de 20 MB de RAM, pero parece que no puedo obtenerlo mucho más pequeño que esto. Inde...

3  Script de filtro más elegante en r  ( More elegant filter script in r ) 
Soy muy nuevo tanto para programar como para que, por favor, tenga en cuenta conmigo :-) He escrito el siguiente bit de código, que funciona perfectamente bie...

1  Intervalo de confianza simultánea  ( Simultaneous confidence interval ) 
Recientemente leí un artículo en el que los autores presentan algoritmo 1 para calcular un intervalo de confianza simultáneo. Me interesaba implementar el a...

3  Acelerando para el bucle sobre una lista  ( Speeding up for loop over a list ) 
Tengo dos listas con ca. 4000 elementos donde cada elemento tienen dos columnas. Estos se están introduciendo en una función. Además de la función en la que s...

4  Código imperativo en r manteniendo un seguimiento del estado  ( Imperative code in r keeping track of state ) 
Un amigo mío tiene una hoja de cálculo donde codificó un video en el aula para varios eventos de enseñanza, que necesitaba para ayudarla. Para cada grabación,...

9  Generador de tabla de verdad para una función arbitraria  ( Truth table generator for an arbitrary function ) 
Summary : esta función genera una tabla de verdad para una función booleana de número de argumentos variables. El nombre de la función pasó y sus argumentos ...

3  Correlación y dependencia  ( Correlation and dependence ) 
Es bien sabido que 0 dependencia implica 0 correlación, mientras que 0 correlación no implica 0 dependencia. Tengo un papel aquí que ilustra los coeficiente...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos