Foro de elhacker.net

Programación => Programación Visual Basic => Mensaje iniciado por: Karcrack en 17 Julio 2010, 14:30 pm



Título: [RETO] Funcion iFactorize() - Factorizacion de numeros enteros
Publicado por: Karcrack en 17 Julio 2010, 14:30 pm
Otro reto; A ver quien hace la funcion de factorizacion mas rapida :)

Se trata de crear una funcion que factorice cualquier numero entero positivo...

La funcion ha de devolver un Collection con todos los numeros primos que componen ese numero

Para medir el tiempo necesario se utilizará este codigo:
Código:
Private tmr     As CTiming

Private Sub Form_Load()
    Dim x       As Long
    Dim vItem   As Variant
   
    Set tmr = New CTiming
    tmr.Reset
   
    For x = 0 To 4096
        'Debug.Print x, ;
        'For Each vItem In iFactorize(x)
        '    Debug.Print vItem;
        'Next vItem
        'Debug.Print
        Call iFactorize(x)
    Next x
   
    MsgBox tmr.sElapsed
End Sub
cTiming.cls (http://www.xbeat.net/vbspeed/download/CTiming.zip)

+Info
Código:
http://en.wikipedia.org/wiki/Integer_factorization
http://es.wikipedia.org/wiki/Factorizaci%C3%B3n_de_enteros

Suerte, espero que participeis muchos :P


Título: Re: [RETO] Funcion iFactorize() - Factorizacion de numeros enteros
Publicado por: Karcrack en 17 Julio 2010, 14:44 pm
v0.1:
Mi funcion tarda: 17,462 msec (Probado compilado, en un procesador de ***** :xD)
Código:
Public Function iFactorize(ByVal n As Long) As Collection
    Dim cTmp    As New Collection
    Dim i       As Long
    Dim lSqrt   As Long
    
    If Not n > 0 Then GoTo Ret
    
    lSqrt = Sqr(n)

    For i = 2 To lSqrt
        If n Mod i = 0 Then
            Set cTmp = iFactorize(n / i)
            cTmp.Add i
            GoTo Ret
        End If
    Next i
    
    cTmp.Add n
    
Ret: Set iFactorize = cTmp
End Function
:D

v0.2:
Código
  1. Public Function iFactorize(ByVal n As Long) As Collection
  2.    Dim cTmp    As New Collection
  3.    Dim i       As Long
  4.  
  5.    If n = 0 Then GoTo Ret
  6.    If n = 1 Then cTmp.Add 1: GoTo Ret
  7.  
  8.    While (n And 1) = 0
  9.        cTmp.Add 2
  10.        n = n / 2
  11.    Wend
  12.  
  13.    i = 3
  14.    While (i <= (n ^ 0.5))
  15.        If (n Mod i) = 0 Then
  16.            cTmp.Add i
  17.            n = n / i
  18.        End If
  19.        i = i + 2
  20.    Wend
  21.  
  22.    If n > 1 Then cTmp.Add n
  23.  
  24. Ret: Set iFactorize = cTmp
  25. End Function


Título: Re: [RETO] Funcion iFactorize() - Factorizacion de numeros enteros
Publicado por: Psyke1 en 17 Julio 2010, 19:37 pm
Ok, me apunto, pero tiene que ser con Collections a la fuerza¿? :-\

DoEvents¡! :P


Título: Re: [RETO] Funcion iFactorize() - Factorizacion de numeros enteros
Publicado por: BlackZeroX en 17 Julio 2010, 21:55 pm
Compilado!¡ 8,817 ms Proc: 2.2Ghz One Core!¡... no es una collection xP

Código
  1.  
  2. Public Function FactorizadorBlackZeroX(ByVal vNumber As Long) As String
  3. Dim i               As Long
  4.    If vNumber < 0 Then Exit Function
  5.    For i = 2 To Sqr(vNumber)
  6.        If vNumber Mod i = 0 Then
  7.            FactorizadorBlackZeroX = FactorizadorBlackZeroX(vNumber / i) & "," & i
  8.            Exit Function
  9.        End If
  10.    Next i
  11.    FactorizadorBlackZeroX = vNumber
  12. End Function
  13.  
  14.  

Source Test:

Código
  1.  
  2. Option Explicit
  3. Private tmr As CTiming
  4. Private Sub Form_Load()
  5. Dim x       As Long
  6. Dim vItem   As Variant
  7. Const limit = 5000
  8. Dim TestResults$
  9.  
  10.    Set tmr = New CTiming
  11.    tmr.Reset
  12.    For x = 0 To limit
  13.        Call FactorizadorBlackZeroX(x)
  14.    Next x
  15.    TestResults$ = "FactorizadorBlackZeroX " & tmr.sElapsed
  16.    tmr.Reset
  17.    For x = 0 To limit
  18.        Call iFactorize2(x)
  19.    Next x
  20.    Call MsgBox(TestResults$ & vbCrLf & "iFactorize2: " & tmr.sElapsed)
  21. End Sub
  22.  
  23.  

Sangriento Infierno Lunar!¡.


Título: Re: [RETO] Funcion iFactorize() - Factorizacion de numeros enteros
Publicado por: BlackZeroX en 17 Julio 2010, 21:59 pm
Se me olvido preguntar la cosa es llegar el menor consumo de procesador?, se vale cualquier maña?...

Dulces Lunas!¡.


Título: Re: [RETO] Funcion iFactorize() - Factorizacion de numeros enteros
Publicado por: Karcrack en 18 Julio 2010, 14:04 pm
La cosa es hacerlo mas rapido posible y hacerlo con COLLECTIONS!! que es la mejor forma de trabajar mas tarde que lo que retorna la funcion...

Tu codigo en mi procesador en el mejor de los casos tarda: 21,551 msec


Título: Re: [RETO] Funcion iFactorize() - Factorizacion de numeros enteros
Publicado por: BlackZeroX en 18 Julio 2010, 21:19 pm
.
Extraño a mi el tuyo me tardo 11.850 ms; creo qué alguien mas debería de hacer los test... Moderador!¡.

Dulces Lunas!¡.


Título: Re: [RETO] Funcion iFactorize() - Factorizacion de numeros enteros
Publicado por: FFernandez en 18 Julio 2010, 22:14 pm
Hola BlackZeroX




                         Soy nuevo y sé poco.

                         Perdona, solo he modificado un poco tu codigo.......


Public Function FactorizadorBlackZeroX(ByVal vNumber As Long) As String
Dim i As Long
Dim TmpArray() As Long

If vNumber < 0 Then Exit Function

If vNumber Mod 2= 0 Then
     FactorizadorBlackZeroX = FactorizadorBlackZeroX(vNumber / 2) & "," & 2
     Exit Function
End If



For i = 3 To Sqr(vNumber) step 2


       If vNumber Mod i = 0 Then
           FactorizadorBlackZeroX = FactorizadorBlackZeroX(vNumber / i) & "," & i
           Exit Function
       End If

Next i


FactorizadorBlackZeroX = vNumber

End Function



                 Espero que sirva...................

                               Un saludo a los dos


Título: Re: [RETO] Funcion iFactorize() - Factorizacion de numeros enteros
Publicado por: BlackZeroX en 18 Julio 2010, 22:46 pm

Compilado:

FactorizadorBlackZeroX: 9.826 msec
iFactorize: 11.000 msec
FactorizadorFFernandez: 8.848 msec

Código
  1.  
  2. Option Explicit
  3. Private tmr As CTiming
  4. Private Sub Form_Load()
  5. Dim x       As Long
  6. Dim vItem   As Variant
  7. Const limit = 5000
  8. Dim TestResults$(2)
  9.  
  10.    Set tmr = New CTiming
  11.    tmr.Reset
  12.    For x = 0 To limit
  13.        Call FactorizadorBlackZeroX(x)
  14.    Next x
  15.    TestResults$(0) = tmr.sElapsed
  16.    tmr.Reset
  17.    For x = 0 To limit
  18.        Call iFactorize(x)
  19.    Next x
  20.    TestResults$(1) = tmr.sElapsed
  21.    tmr.Reset
  22.    For x = 0 To limit
  23.        Call FactorizadorFFernandez(x)
  24.    Next x
  25.    TestResults$(2) = tmr.sElapsed
  26.    MsgBox "FactorizadorBlackZeroX: " & TestResults$(0) & vbCrLf & _
  27.           "iFactorize: " & TestResults$(1) & vbCrLf & _
  28.           "FactorizadorFFernandez: " & TestResults$(2)
  29. End Sub
  30.  
  31. Public Function iFactorize(ByVal n As Long) As Collection
  32.    Dim cTmp    As New Collection
  33.    Dim i       As Long
  34.    Dim lSqrt   As Long
  35.  
  36.    If Not n > 0 Then GoTo Ret
  37.  
  38.    lSqrt = Sqr(n)
  39.  
  40.    For i = 2 To lSqrt
  41.        If n Mod i = 0 Then
  42.            Set cTmp = iFactorize(n / i)
  43.            cTmp.Add i
  44.            GoTo Ret
  45.        End If
  46.    Next i
  47.  
  48.    cTmp.Add n
  49.  
  50. Ret: Set iFactorize = cTmp
  51. End Function
  52.  
  53. Public Function FactorizadorFFernandez(ByVal vNumber As Long) As String
  54. Dim i As Long
  55.    If vNumber <= 0 Then Exit Function
  56.    If vNumber Mod 2 = 0 Then
  57.         FactorizadorFFernandez = FactorizadorFFernandez(vNumber / 2) & "," & 2
  58.         Exit Function
  59.    End If
  60.    For i = 3 To Sqr(vNumber) Step 2
  61.       If vNumber Mod i = 0 Then
  62.           FactorizadorFFernandez = FactorizadorFFernandez(vNumber / i) & "," & i
  63.           Exit Function
  64.       End If
  65.    Next i
  66.    FactorizadorFFernandez = vNumber
  67. End Function
  68.  
  69. Public Function FactorizadorBlackZeroX(ByVal vNumber As Long) As String
  70. Dim i               As Long
  71.    If vNumber < 0 Then Exit Function
  72.    For i = 2 To Sqr(vNumber)
  73.        If vNumber Mod i = 0 Then
  74.            FactorizadorBlackZeroX = FactorizadorBlackZeroX(vNumber / i) & "," & i
  75.            Exit Function
  76.        End If
  77.    Next i
  78.    FactorizadorBlackZeroX = vNumber
  79. End Function
  80.  
  81.  



Título: Re: [RETO] Funcion iFactorize() - Factorizacion de numeros enteros
Publicado por: Karcrack en 18 Julio 2010, 23:09 pm
Vuestras funciones no cumplen el requisito de devolver Collections! Asi que yo gano ::) (:P :rolleyes:)


Título: Re: [RETO] Funcion iFactorize() - Factorizacion de numeros enteros
Publicado por: BlackZeroX en 18 Julio 2010, 23:21 pm
.
Las colecciones jamas me han convencido las veo lentas ¬¬"  >:D mejor un Array vale  :xD  >:D

Dulces Lunas!¡.


Título: Re: [RETO] Funcion iFactorize() - Factorizacion de numeros enteros
Publicado por: Karcrack en 18 Julio 2010, 23:52 pm
He actualizado mi codigo! ;) , no me ha dado tiempo a comprobar la velocidad, doy por hecho que es mas rapida porque no es recursiva :-\

Lo de las collections es el requisito basico para el reto...


Título: Re: [RETO] Funcion iFactorize() - Factorizacion de numeros enteros
Publicado por: seba123neo en 19 Julio 2010, 05:32 am
Karcrack y a TODOS me gustarian que pongan las caracteristicas de la maquina donde estan probando, procesador y RAM, como para ver en que condiciones se esta probando, yo pruebo el ejemplo de Karcrack compilado obviamente y me da 4 veces mas de tiempo del que pusiste, es una notebook Intel Core 2 Duo 2Ghz y 3 GB de ram, o sea es una "buena" maquina. lo de las Collections quedo claro, BlackZeroX hacelo con Collections, debe haber miles de ejemplos mas rapidos con arrays, pero tiene que devolver lo que se dijo en el primer post y hay que cumplir las reglas  :xD



Título: Re: [RETO] Funcion iFactorize() - Factorizacion de numeros enteros
Publicado por: Karcrack en 19 Julio 2010, 13:29 pm
Por decirlo de una forma suave y que se entienda, lo de los collections es porque me sale de los huevos >:D :laugh: :laugh: :laugh:

Pues en el portatil que lo probe tiene un Mobile Intel Pentium M LV, 1200 MHz (12 x 100) y 512MB de RAM... Una mierdecilla...


Título: Re: [RETO] Funcion iFactorize() - Factorizacion de numeros enteros
Publicado por: Angeldj27 en 19 Julio 2010, 15:21 pm
Hay va la mia

Código
  1. Public Function FactorizeS(ByVal S As Long) As Collection  
  2.    Dim cTmp    As New Collection
  3.    Dim I       As Long
  4.  
  5.   If S <= 0 Then GoTo Ret
  6.   If S = 1 Then cTmp.Add 1: GoTo Ret
  7.  
  8.   For I = 2 To Sqr(S)
  9.        If S Mod I = 0 Then
  10.           cTmp.Add I
  11.       End If
  12.       I = I + 2
  13.   Next I
  14.  
  15. Ret: Set FactorizeS = cTmp
  16. End Function
  17.  

Claro casimente es una mejora a las otras funciones pero es mas rapida  ;D


Título: Re: [RETO] Funcion iFactorize() - Factorizacion de numeros enteros
Publicado por: FFernandez en 19 Julio 2010, 17:19 pm
Hola Angeldj27



                          Prueba factorizar el nº 49.



                                                Un saludo