$2$ QUESITI: $1$ Matematico ed $1$ Informatico; Numero di Iterazioni per estrarre radice intera.

[curie88]

Buona sera, vi ripropongo in questa sezione, i seguenti due quesiti/giochi(che avevo proposto nella sezione giochi, ma dato l'argomento, e le risposte ricevute, probabilmente essa non era adatta), del primo gradirei una vostra risposta dimostrativa e matematica(che io non conosco), ma anche una soluzione vostra numerica, può bastare(da confrontare); del secondo invece richiedo una risposta informatica; vostro pseudo-codice oppure un algoritmo.(da confrontare)

DIMOSTRAZIONE MATEMATICA:
1) Quante iterazioni sono necessarie per poter estrarre la radice quadrata intera $x=\lfloor\sqrt(987654321)\rfloor$ ?
[ Nel gioco propongo sostanzialmente di riuscire a calcolare detta radice, nel minor numero di iterazioni. Come detto, non ho ancora ricercato la soluzione matematica(dimostrativa) al quesito(sebbene ho alcune soluzioni) però sarei piuttosto curioso di conoscerla; ed intuitivamente deve pur esistere. ]

IMPLEMENTAZIONE DI UN ALGORITMO(c/cpp/java/javascript/basic/pascal...) O PSEUDO CODICE:
2) Quale algoritmo/pseudo codice realizzereste per poter eseguire l' operazione di radice quadrata(con in input ed in output, numeri interi) nel minor numero di iterazioni?

[Obidream]

Al di là dei quesiti ( probabilmente mi cimenterò sul 2) perché parli solo di iterazioni? Ci sono alcuni metodi in "forma chiusa" che quindi sono iterativi

[curie88]

Qui sono interessato ad ottimizzare i calcoli, non la memoria in uso. Se ho inteso ciò che intendi. Saluti.

[Obidream]

No, non intendevo l'uso della memoria.

Codice:

#include <inttypes.h>
#define two_to_pow_30 0x40000000
#define two_to_pow_15 0x8000

static uint32_t isqrt(uint32_t val)
{
    uint32_t temp, g = 0;

    if (val >= two_to_pow_30) {
        g = two_to_pow_15;
        val -= two_to_pow_30;
    }

    #define INNER_ISQRT(s)                        \
        temp = (g << (s)) + (1 << (((s) << 1) - 2));   \
        if (val >= temp) {                          \
            g += 1 << ((s) - 1);                        \
            val -= temp;                              \
        }

    INNER_ISQRT (15)
    INNER_ISQRT (14)
    INNER_ISQRT (13)
    INNER_ISQRT (12)
    INNER_ISQRT (11)
    INNER_ISQRT (10)
    INNER_ISQRT (9)
    INNER_ISQRT (8)
    INNER_ISQRT (7)
    INNER_ISQRT (6)
    INNER_ISQRT (5)
    INNER_ISQRT (4)
    INNER_ISQRT (3)
    INNER_ISQRT (2)
    #undef INNER_ISQRT

    temp = g + g + 1;
    if (val >= temp) {
        ++g;
    }

    return g;
}

Comunque userei questo per il punto 2 che come dicevo non compie alcuna iterazione, dove per iterazione s'intende la ripetizione di una determinata istruzione, una roba del tipo:

Codice:

a = 0;
for(i = 0; i <= 3; ++i) {
    a += i;
}


[curie88]

Appena ho tempo lo testo, grazie, in seguito posterò il codice(java), potresti solo dirmi quante iterazioni esegue il tuo programma per il calcolo del radicando: $987654321$?

[Obidream]

Se per iterazioni intendi questo sono 14, ovvero le volte in cui la macro INNER_SQRT viene usata. Si potrebbe anche fare con un ciclo for ma almeno con il mio compilatore e sul mio hardware risulta più lento, la cosa interessante è che il numero di iterazioni non dipende dal numero in input chiaramente.

[curie88]

Si intendevo proprio questo per iterazione. Il tuo hardware è molto datato?
Questo codice, piuttosto elementare, in java, stampa il numero di iterazioni di volta in volta, per intenderci; solamente che pur girando piuttosto bene, almeno sul mio hardware, le iterazioni mi risultano $38$.

Codice:

    private static int radInt(int x){                 
        int y=x;
        String s = Integer.toString((int)x);
        int lng = s.length();
        int t;
        int k=0;
        int SqX=y/2;       
        if (lng<=2) {             
            while (SqX > 1+(y-1)/(1+SqX)){     
             System.out.println(SqX);
             SqX--;
             k++;
             System.out.println(k);
            }
        }
        else {                       
            int l=lng/2;
            t = (int)Math.pow(10,l-1);
                System.out.println(SqX);
                k++;
                System.out.println(k);
            SqX/=t;                           

            while (SqX/2 > 1+(y-1)/(1+SqX/2)){
                System.out.println(SqX);
                k++;
                System.out.println(k);
            SqX/=2;
            } 
            while (SqX >= 1+(y-1)/(1+SqX) && t>0) {
            while (SqX-t >= 1+(y-1)/(1+SqX-t)){
                System.out.println(SqX+"t:"+t);               
                k++;
                System.out.println(k);
            SqX-=t;
            }
            t/=10;
            }     
            while (SqX > 1+(y-1)/(1+SqX)) SqX--;
            System.out.println(k);
        }                             
        return SqX;
    }


[Obidream]

No intendevo un'altra cosa, in pratica con un compilatore C puoi vedere il relativo output assembly ed ho notato che sostituisco tutte quelle macro consecutive con un for il codice è più lento perché evidentemente non lo ottimizza come vorrei.
Comunque la velocità su un singolo numero è irrilevante, per renderti conto delle differenze dovresti provare con zilioni di numeri, una cosa del genere:

Codice:

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#define two_to_pow_30 0x40000000
#define two_to_pow_15 0x8000

static uint32_t isqrt (uint32_t val)
{
    uint32_t temp, g=0;

    if (val >= two_to_pow_30) {
        g = two_to_pow_15;
        val -= two_to_pow_30;
    }

    #define INNER_ISQRT(s)                        \
        temp = (g << (s)) + (1 << (((s) << 1) - 2));   \
        if (val >= temp) {                          \
            g += 1 << ((s) - 1);                        \
            val -= temp;                              \
        }

    INNER_ISQRT (15u)
    INNER_ISQRT (14u)
    INNER_ISQRT (13u)
    INNER_ISQRT (12u)
    INNER_ISQRT (11u)
    INNER_ISQRT (10u)
    INNER_ISQRT ( 9u)
    INNER_ISQRT ( 8u)
    INNER_ISQRT ( 7u)
    INNER_ISQRT ( 6u)
    INNER_ISQRT ( 5u)
    INNER_ISQRT ( 4u)
    INNER_ISQRT ( 3u)
    INNER_ISQRT ( 2u)

    #undef INNER_ISQRT

    temp = g + g + 1;
    if (val >= temp) {
        ++g;
    }

    return g;
}

int main(void)
{
    for(uint32_t i = 0; i <= 1000000; ++i) {
        printf("isqrt(%" PRIu32 ") = %" PRIu32 "\n", i, isqrt(i));
    }
    return EXIT_SUCCESS;
}



Non confrontare il tempo d'esecuzione tra Java e C, sono linguaggi diversi per cui non avrebbe senso.
Per il primo quesito consiglio questo libro: c'è un paragrafo ( dovrebbe essere più sopra, si chiama The Friden Algorithm) dove illustra un algoritmo che veniva usato per calcolare la radice quadrata intera con un calcolatore in grado di svolgere solo le 4 operazione base.

[curie88]

No intendevo un'altra cosa, in pratica con un compilatore C puoi vedere il relativo output assembly ed ho notato che sostituisco tutte quelle macro consecutive con un for il codice è più lento perché evidentemente non lo ottimizza come vorrei.
Comunque la velocità su un singolo numero è irrilevante, per renderti conto delle differenze dovresti provare con zilioni di numeri, una cosa del genere:

L'assembly lo conosco pochissimo, ed anche il c, tuttavia ho lasciato libero spazio alla mia domanda in modo da ricevere buone risposte, convinto anche tutt' ora, che chi conosce il c sappia ben programmare.
A prescindere dal linguaggio usato, sono ovviamente interessato sopratutto al risultato, tant' é che sono anche curioso di avere una risposta in tutto e per tutto matematica al quesito(che forse tu hai trovato, ed è $14$?), che è molto probabile sia è stata, e forse anche da secoli, scoperta.

Ho già rielaborato il codice della funzione, sostituendo il suo valore di Input da Int a BigInteger, e per quanto riguarda la capacità di trasformare il radicando nella sua radice, essa sembra non avere alcun problema, anche nella velocità di calcolo.

Resta un fatto differente, tra i nostri codici, che nel mio il numero di ripetizioni di calcoli elementari(che è ciò che intendo, e forse erroneamente, con il termine iterazione), cresce con la lunghezza del radicando, mentre nel tuo, stando a quello che mi hai scritto, resta costante ed uguale a $14$. Poiché necessito di più tempo per assimilare i codici da te postati, non mi è chiaro il motivo di questa differenza. Il confronto matematico dovrebbe essere indipendente dal linguaggio informatico usato.
Avrei forse dovuto richiedere solamente un diagramma di flusso, ma non avrei(mai) potuto testare direttamente i codici.
Ora provo a leggere il libro da te consigliatomi per il primo quesito.

Buona serata e grazie intanto per l' intervento.

[curie88]

Se per iterazioni intendi questo sono 14, ovvero le volte in cui la macro INNER_SQRT viene usata. Si potrebbe anche fare con un ciclo for ma almeno con il mio compilatore e sul mio hardware risulta più lento, la cosa interessante è che il numero di iterazioni non dipende dal numero in input chiaramente.

Quindio anche per calcolare la radice di $4$, il numero minimo di iterazioni è $14$? Possibile?