[RETO] Project Euler 1

[MCKSys Argentina]

Nueva función:

Código (vb) [Seleccionar] Expandir


Public Function Euler_1(ByVal lNum As Long) As Long
Dim S5 As Long

    If lNum& And &H80000000 Then Exit Function

    lNum& = lNum& - &H1
   
    Euler_1& = ((lNum& \ &HF) * ((lNum& \ &HF) + 1) \ 2) * &HF
   
    S5& = ((lNum& \ &H5) * ((lNum& \ &H5) + 1) \ 2) * &H5
   
    Euler_1& = S5& - Euler_1&
   
    Euler_1& = Euler_1& + (((lNum& \ &H3) * ((lNum& \ &H3) + 1) \ 2) * &H3)
End Function


Compilados, estos son los tiempos:

Código [Seleccionar] Expandir


Tiempo BlackZeroX V2        66.052 msec
Resultado BlackZeroX V2     233168

Tiempo BlackZeroX V1        43.226 msec
Resultado BlackZeroX V1     233168

Tiempo 7913   144.274 msec
Resultado 7913              233168

Tiempo dany   1,635.416 msec
Resultado dany              233168

Tiempo Spyke1 176.800 msec
Resultado Spyke1            233168

Tiempo MCKSys 0.983 msec
Resultado MCKSys            233168



Estoy desvelado y no lo puedo creer aún, así que verifiquen!!!!!!!!!!!

Saludos!

[BlackZeroX]

PD: Mirando el ASM generado, veo que el secreto está en no usar multiplicaciones ni divisiones.

Si no mal recuerdo de mis clases la base del procesamiento numérico de una computadora esta en la SUMA...

Se zarpaste con esas operaciones aun que NO funciona para varios números!¡... Probé tu función y la mía (Debido a la alta complejidad) con la función de Spyke1...

Código (vb) [Seleccionar] Expandir


Const MAX_FOR   As Long = 10000
Dim i as long

   For i = 1 To MAX_FOR
       If Not (PE_1(i) = Euler_1(i)) Then
           Debug.Print "BlackZeroX Error: "; i
       End If
   Next
   
   For i = 1 To MAX_FOR
       If Not (PE_1(i) = mul3and5(i)) Then
           Debug.Print "MCKSys Argentina Error: "; i
       End If
   Next


Son mas errores pero me corta las primeras salidas el Debug...

Código [Seleccionar] Expandir


MCKSys Argentina Error:  7038
MCKSys Argentina Error:  7053
MCKSys Argentina Error:  7068
MCKSys Argentina Error:  7083
MCKSys Argentina Error:  7098
MCKSys Argentina Error:  7113
MCKSys Argentina Error:  7128
MCKSys Argentina Error:  7143
MCKSys Argentina Error:  7158
MCKSys Argentina Error:  7173
MCKSys Argentina Error:  7188
MCKSys Argentina Error:  7203
MCKSys Argentina Error:  7218
MCKSys Argentina Error:  7233
MCKSys Argentina Error:  7248
MCKSys Argentina Error:  7263
MCKSys Argentina Error:  7278
MCKSys Argentina Error:  7293
MCKSys Argentina Error:  7308
MCKSys Argentina Error:  7323
MCKSys Argentina Error:  7338
MCKSys Argentina Error:  7353
MCKSys Argentina Error:  7368
MCKSys Argentina Error:  7383
MCKSys Argentina Error:  7398
MCKSys Argentina Error:  7413
MCKSys Argentina Error:  7428
MCKSys Argentina Error:  7443
MCKSys Argentina Error:  7458
MCKSys Argentina Error:  7473
MCKSys Argentina Error:  7488
MCKSys Argentina Error:  7503
MCKSys Argentina Error:  7518
MCKSys Argentina Error:  7533
MCKSys Argentina Error:  7548
MCKSys Argentina Error:  7563
MCKSys Argentina Error:  7578
MCKSys Argentina Error:  7593
MCKSys Argentina Error:  7608
MCKSys Argentina Error:  7623
MCKSys Argentina Error:  7638
MCKSys Argentina Error:  7653
MCKSys Argentina Error:  7668
MCKSys Argentina Error:  7683
MCKSys Argentina Error:  7698
MCKSys Argentina Error:  7713
MCKSys Argentina Error:  7728
MCKSys Argentina Error:  7743
MCKSys Argentina Error:  7758
MCKSys Argentina Error:  7773
MCKSys Argentina Error:  7788
MCKSys Argentina Error:  7803
MCKSys Argentina Error:  7818
MCKSys Argentina Error:  7833
MCKSys Argentina Error:  7848
MCKSys Argentina Error:  7863
MCKSys Argentina Error:  7878
MCKSys Argentina Error:  7893
MCKSys Argentina Error:  7908
MCKSys Argentina Error:  7923
MCKSys Argentina Error:  7938
MCKSys Argentina Error:  7953
MCKSys Argentina Error:  7968
MCKSys Argentina Error:  7983
MCKSys Argentina Error:  7998
MCKSys Argentina Error:  8013
MCKSys Argentina Error:  8028
MCKSys Argentina Error:  8043
MCKSys Argentina Error:  8058
MCKSys Argentina Error:  8073
MCKSys Argentina Error:  8088
MCKSys Argentina Error:  8103
MCKSys Argentina Error:  8118
MCKSys Argentina Error:  8133
MCKSys Argentina Error:  8148
MCKSys Argentina Error:  8163
MCKSys Argentina Error:  8178
MCKSys Argentina Error:  8193
MCKSys Argentina Error:  8208
MCKSys Argentina Error:  8223
MCKSys Argentina Error:  8238
MCKSys Argentina Error:  8253
MCKSys Argentina Error:  8268
MCKSys Argentina Error:  8283
MCKSys Argentina Error:  8298
MCKSys Argentina Error:  8313
MCKSys Argentina Error:  8328
MCKSys Argentina Error:  8343
MCKSys Argentina Error:  8358
MCKSys Argentina Error:  8373
MCKSys Argentina Error:  8388
MCKSys Argentina Error:  8403
MCKSys Argentina Error:  8418
MCKSys Argentina Error:  8433
MCKSys Argentina Error:  8448
MCKSys Argentina Error:  8463
MCKSys Argentina Error:  8478
MCKSys Argentina Error:  8493
MCKSys Argentina Error:  8508
MCKSys Argentina Error:  8523
MCKSys Argentina Error:  8538
MCKSys Argentina Error:  8553
MCKSys Argentina Error:  8568
MCKSys Argentina Error:  8583
MCKSys Argentina Error:  8598
MCKSys Argentina Error:  8613
MCKSys Argentina Error:  8628
MCKSys Argentina Error:  8643
MCKSys Argentina Error:  8658
MCKSys Argentina Error:  8673
MCKSys Argentina Error:  8688
MCKSys Argentina Error:  8703
MCKSys Argentina Error:  8718
MCKSys Argentina Error:  8733
MCKSys Argentina Error:  8748
MCKSys Argentina Error:  8763
MCKSys Argentina Error:  8778
MCKSys Argentina Error:  8793
MCKSys Argentina Error:  8808
MCKSys Argentina Error:  8823
MCKSys Argentina Error:  8838
MCKSys Argentina Error:  8853
MCKSys Argentina Error:  8868
MCKSys Argentina Error:  8883
MCKSys Argentina Error:  8898
MCKSys Argentina Error:  8913
MCKSys Argentina Error:  8928
MCKSys Argentina Error:  8943
MCKSys Argentina Error:  8958
MCKSys Argentina Error:  8973
MCKSys Argentina Error:  8988
MCKSys Argentina Error:  9003
MCKSys Argentina Error:  9018
MCKSys Argentina Error:  9033
MCKSys Argentina Error:  9048
MCKSys Argentina Error:  9063
MCKSys Argentina Error:  9078
MCKSys Argentina Error:  9093
MCKSys Argentina Error:  9108
MCKSys Argentina Error:  9123
MCKSys Argentina Error:  9138
MCKSys Argentina Error:  9153
MCKSys Argentina Error:  9168
MCKSys Argentina Error:  9183
MCKSys Argentina Error:  9198
MCKSys Argentina Error:  9213
MCKSys Argentina Error:  9228
MCKSys Argentina Error:  9243
MCKSys Argentina Error:  9258
MCKSys Argentina Error:  9273
MCKSys Argentina Error:  9288
MCKSys Argentina Error:  9303
MCKSys Argentina Error:  9318
MCKSys Argentina Error:  9333
MCKSys Argentina Error:  9348
MCKSys Argentina Error:  9363
MCKSys Argentina Error:  9378
MCKSys Argentina Error:  9393
MCKSys Argentina Error:  9408
MCKSys Argentina Error:  9423
MCKSys Argentina Error:  9438
MCKSys Argentina Error:  9453
MCKSys Argentina Error:  9468
MCKSys Argentina Error:  9483
MCKSys Argentina Error:  9498
MCKSys Argentina Error:  9513
MCKSys Argentina Error:  9528
MCKSys Argentina Error:  9543
MCKSys Argentina Error:  9558
MCKSys Argentina Error:  9573
MCKSys Argentina Error:  9588
MCKSys Argentina Error:  9603
MCKSys Argentina Error:  9618
MCKSys Argentina Error:  9633
MCKSys Argentina Error:  9648
MCKSys Argentina Error:  9663
MCKSys Argentina Error:  9678
MCKSys Argentina Error:  9693
MCKSys Argentina Error:  9708
MCKSys Argentina Error:  9723
MCKSys Argentina Error:  9738
MCKSys Argentina Error:  9753
MCKSys Argentina Error:  9768
MCKSys Argentina Error:  9783
MCKSys Argentina Error:  9798
MCKSys Argentina Error:  9813
MCKSys Argentina Error:  9828
MCKSys Argentina Error:  9843
MCKSys Argentina Error:  9858
MCKSys Argentina Error:  9873
MCKSys Argentina Error:  9888
MCKSys Argentina Error:  9903
MCKSys Argentina Error:  9918
MCKSys Argentina Error:  9933
MCKSys Argentina Error:  9948
MCKSys Argentina Error:  9963
MCKSys Argentina Error:  9978
MCKSys Argentina Error:  9993
[code]

Dulces Lunas!¡.[/code]

[imoen]

Hola

Una pregunta chicos , con la velocidad de los codigos , jeje, veamos dos cosas

A) Sabeis que para medir la velocidad debeis de usar el mismo equipo ?¿?¿ puesto que cad aprocessador aportara distintas velocidades, en esto incluso afectara el sistema operativo y la velocidad de la ram.

B) Un codigo un poco mas rapido no puede ser a costa de ofuscar el codigo o hacer como he visto por hay CT+CT+ct .... asi hasta el infinito y mas alla , para eso se invento los incrementadores add ct,ct.

C) exacto no usar divi y multiplicaciones hace uqe la velocidad aumente pero y si en vez de eso usais los movimientos de bytes ?¿( correr bytes)

bueno eso son mis opiniones
bs imoen

[MCKSys Argentina]

Si no mal recuerdo de mis clases la base del procesamiento numérico de una computadora esta en la SUMA...

Se zarpaste con esas operaciones aun que NO funciona para varios números!¡... Probé tu función y la mía (Debido a la alta complejidad) con la función de Spyke1...

Código (vb) [Seleccionar] Expandir


Const MAX_FOR   As Long = 10000
Dim i as long

    For i = 1 To MAX_FOR
        If Not (PE_1(i) = Euler_1(i)) Then
            Debug.Print "BlackZeroX Error: "; i
        End If
    Next
   
    For i = 1 To MAX_FOR
        If Not (PE_1(i) = mul3and5(i)) Then
            Debug.Print "MCKSys Argentina Error: "; i
        End If
    Next


Son mas errores pero me corta las primeras salidas el Debug...

Código [Seleccionar] Expandir


MCKSys Argentina Error:  7038
MCKSys Argentina Error:  7053
...
...
...
MCKSys Argentina Error:  9963
MCKSys Argentina Error:  9978
MCKSys Argentina Error:  9993
[code]

Dulces Lunas!¡.[/code]

Me parece que están al revés. Euler_1 es mi función y mul3and5 es la tuya. 

[BlackZeroX]

en VB 6 no existe los operadores para desplazamiento de bits... para simularlo los multiplicamos o dividimos según sea el caso...

Código [Seleccionar] Expandir


a << 1 // Desplazamiento de 1 a la izquierda en C/C++.
a * 2 // Simulación en vb6 y en cualquier lenguaje.

a << 4 // Desplazamiento de 4 bits a la izquierda en C/C++.
a * 16 // Simulacion en vb6 y en cualquier lenguaje.

a >> 1 // Desplazamiento de 1 bit a la derecha en C/C++
a \ 2 // No ocupar / ya que devuelve decimales...

a >> 4 // Desplazamiento de 4 bits a la derecha en C/C++
a \ 16 // No ocupar / ya que devuelve decimales...


La cosa de estos retos es generar códigos con las LIMITACIONES que nos da el lenguaje.

* La velocidades SON RELATIVAS no importa el procesador puesto que se podría hacer una simple regla de 3!¡, es decir si una función es mas rápida en procesarse que otra en un procesador que dura Y tiempo, este mismo tiempo será relativo en otro procesador con un tiempo Y +/- Mili-segundos... Has la prueba y veras... Las velocidades son aproximadas.

---->

Había puesto mal el código de prueba ya lo corregí (mi versión V2 JAMA se llamaba).

Código [Seleccionar] Expandir


Tiempo 7913   872.496 msec
Resultado 7913              233168

Tiempo dany   1,650.228 msec
Resultado dany              233168

Tiempo Spyke1 480.171 msec
Resultado Spyke1            233168

Tiempo BlackZeroX V1        202.318 msec
Resultado BlackZeroX V1     233168

Tiempo BlackZeroX V2        129.462 msec
Resultado BlackZeroX V2     233168

Tiempo MCKSys Argentina     7.249 msec
Resultado MCKSys Argentina  233168



Dulces Lunas!¡.

[BlackZeroX]

Me parece que están al revés. Euler_1 es mi función y mul3and5 es la tuya. 

Madre que me desvelo son las 06:00 am y no e dormido.

->> Error Corregido las dos funciones trabajan perfecto... Madre todo por un "="

Lineas 21 (Versión 1) y 31 (Versión 2) de mi funciones respectivas

Código (vb) [Seleccionar] Expandir


                    If (i > dwBelowTo) Then Exit Function

To

Código (vb) [Seleccionar] Expandir


                    If (i >= dwBelowTo) Then Exit Function


Dulces Lunas!¡.

[MCKSys Argentina]

Madre que me desvelo son las 06:00 am y no e dormido.

Dulces Lunas!¡.

jejeje.. estamos igual 

De todas formas, estuve probando hasta 20000 y mi función no genera errores (Comparada con la de Psyke1).

Creo que fue buena idea sacrificar los bucles por las multiplicaciones y divisiones...  

[BlackZeroX]

Creo que fue buena idea sacrificar los bucles por las multiplicaciones y divisiones... 

Ya ando trabajando en algo...

Dulces Lunas!¡.

[BlackZeroX]

Esta es la tercera versión... mejore el tiempo pero que alguien compruebe compilado!¡.

Código [Seleccionar] Expandir


Tiempo 7913   930.892 msec
Resultado 7913              233168

Tiempo dany   1,693.349 msec
Resultado dany              233168

Tiempo Spyke1 521.769 msec
Resultado Spyke1            233168

Tiempo BlackZeroX V1        234.119 msec
Resultado BlackZeroX V1     233168

Tiempo BlackZeroX V2        130.859 msec
Resultado BlackZeroX V2     233168

Tiempo BlackZeroX V3        6.550 msec
Resultado BlackZeroX V3     233168

Tiempo MCKSys Argentina     10.054 msec
Resultado MCKSys Argentina  233168


Código (vb) [Seleccionar] Expandir


Public Function mul3and5_Ver3(Optional ByVal dwBelowTo As Long = &H3E8&) As Long
Dim N As Long
Dim M As Long
Dim I As Long
   If (dwBelowTo < &H4) Then Exit Function
   dwBelowTo = (dwBelowTo - &H1)
   N = dwBelowTo \ &H3
   M = dwBelowTo \ &H5
   I = M \ &H3
   mul3and5_Ver3 = (&H3 * N * (N + &H1) \ &H2) + (&H5 * ((M * (M + &H1) \ &H2) - &H3 * (I * (I + &H1) \ &H2)))
End Function


Les dejo mi Análisis que anduve asiendo en el Block de Notas... Algo similar hice en las versiones anteriores.
Lo que trato de obtener son simples formulas de series numéricas bajo patrones...

/*
01 02 03 04 05 06 07 08 09 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30

Cantidad múltiplos de 3 = 10 <--- Tomamos TODOS los múltiplos de 3 (3, 6, 9, 12, 15, 18, 21, 24, 27, 30, ...)

01 02    04 05    07 08    10
11    13 14    16 17    19 20
  22 23    25 26    28 29    

Cantidad múltiplos de 5 = 6
Removiendo múltiplos de 3 que se repitan en los de 5 = 4 múltiplos de 5 son los que quedan.
Se recurre en un patrón de 2 múltiplos de 5 y el siguiente se excluye por que será múltiplo de 3 como se ve en los números anteriores ( 5, 10, 20, 25, 35, 40, ...).

Por lo tanto Para 30

=1(3) + 2(3) + 3(3) + 4(3) + 5(3) + 6(3) + 7(3) + 8(3) + 9(3) + 10(3)
=3 * (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10) <--- Se genera una sumatoria multiplicada por 3.
=3 * 10 * (10 + 1) \ 2
Por lo tanto:
z = Numero Máximo.
N = Z \ 3
= 3 * N * (N + 1) \ 2 <--- Formula trozo 1 Ok...


= 1(5) + 2(5) + 4(5) + 5(5)
= 5 * (1 + 2 + 4 + 5) <-- Casi se genera una sumatoria así que sumo 3 y resto 3 ( 3-3 = 0 ) esto no importa no afecta...
= 5 * (1 + 2 + 3 + 4 + 5 - 3) <-- Sumatoria que se le resta 3 y a su resultado se multiplica 5.
= 5 * (5 * (5 + 1) \ 2 - 3)
Por lo tanto:
z = Numero Máximo.
N = Z \ 5
= 5 * (N * (N + 1) \ 2 - 3 ) <-- Aun falta corroborar si no hay que multiplicar o dividir ese -3 por lo tanto Expando...


= 5 * (1 + 2 + 4 + 5 + 7 + 8 + 10 + 11)
= 5 * (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11    - 3 - 6 - 9)
= 5 * (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11    - 3(1 + 2 + 3)) <-- Si habia algo que hacerle a ese -3 se le multipplicaba por una sumatoria.
= 5 * (11 * (11 + 1) \ 2        - 3 ( 3 * (3 + 1) \ 2))
Por lo tanto:
z = Numero Máximo.
M = Z \ 5
I = M \ 3
= 5 * ((M * (M + 1) \ 2) - 3 ( I * (I + 1) \ 2)) <-- Formula trozo 2 Ok

Por lo tanto para calcular la sumatoria de los múltiplos de 3 y 5 es:

(3 * N * (N + 1) \ 2 + N) + (5 * ((M * (M + 1) \ 2) - 3 * (I * (I + 1) \ 2)))
Donde:
z = Numero Máximo.
N = Z \ 3
M = Z \ 5
I = M \ 3
Todas las divisiones son en ENTEROS "\"

*/

--> Edito

Me estoy dando cuenta que el código es SIMILAR pero no igual al de MCKSys Argentina (Saca una sumatoria hasta 15, en base a un análisis similar)... me di cuenta ya tarde...

Dulces Lunas!¡.

[Danyfirex]

Bueno aquí dejo  mi otra funcion un poco mas optima que las anteriores ("mias") 

Código (vb) [Seleccionar] Expandir

Function mul_3_5(numero As Long) As Long
Dim a, b, c, d, e, f, g, i As Integer
a = 3
b = 2
c = 1
d = 3
e = 1
f = 2
g = 3
i = 0
While i < numero
i = i + a
mul_3_5 = mul_3_5 + i
If i = numero - 1 Then Exit Function
i = i + b
mul_3_5 = mul_3_5 + i
If i = numero - 1 Then Exit Function
i = i + c
mul_3_5 = mul_3_5 + i
If i = numero - 1 Then Exit Function
i = i + d
mul_3_5 = mul_3_5 + i
If i = numero - 1 Then Exit Function
i = i + e
mul_3_5 = mul_3_5 + i
If i = numero - 1 Then Exit Function
i = i + f
mul_3_5 = mul_3_5 + i
If i = numero - 1 Then Exit Function
i = i + g
mul_3_5 = mul_3_5 + i
If i = numero - 1 Then Exit Function
Wend

End Function


Muy Rápidas  las de  BlackZeroX  & MCKSys Argentina 


saludos