0votos

Descomposiciones como suma de dos cuadrados en JavaScript

por josejuan hace 6 años

Coste lineal con operaciones básicas (suma y desplazamiento de bits). Igual se puede mejorar, pero no recuerdo ninguna propiedad de los triángulos con lados enteros y ahora no tengo tiempo (estoy de paso ;) ). La misma versión en C es muchísimo más rápida, claro...

Descomponer un número como suma de dos cuadrados.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function s2c(n) { 
    var y = ~~(Math.ceil(Math.sqrt(n >> 1))); 
    var x = y, z = (x * x) << 1; 
    while(x >= 0) { 
        if(z == n) console.log("(" + x + ", " + y + ")"); 
        if(z < n) z += (y++ << 1) + 1; 
        else      z -= (x-- << 1) - 1; 
 
 
 
 
//  
var t0 = new Date(); 
s2c(10000000009) 
var t1 = new Date(); 
console.log("t ~ " + (t1 - t0)) 
 
/* 
(21597, 97640) 
(3, 100000) 
t ~ 6 milisegundos 
*/ 
3 comentarios
0votos

Escrito por josejuan hace 6 años

Sólo hay que ver que dados 'x' e 'y', si es z < n entonces hay que incrementar 'y' mientras que si es z > n entonces hay que decrementar 'x'.

Tanto 'x' como 'y' parten de la raíz de 'n' (caso de ser 'n' el doble de un cuadrado perfecto).

Para sumar y restar incrementos basta ver que (Yn1)^2 = (Yn)^2 2 Yn + 1
0votos

Escrito por josejuan hace 6 años

(arg!!! la última frase es)

Para sumar y restar incrementos basta ver que [Yn + 1]^2 = [Yn]^2 2 Yn + 1

(se me come los mases....)
0votos

Escrito por josejuan hace 6 años

(argggg!!!!)

Para sumar y restar incrementos basta ver que "el cuadrado del siguiente, es el cuadrado del anterior, más el doble del anterior, más uno".

(arf!)

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.