[C] Estrarre le cifre di un numero

Forum dedicato alla programmazione.

Moderatore: Staff

Regole del forum
1) Citare in modo preciso il linguaggio di programmazione usato.
2) Se possibile portare un esempio del risultato atteso.
3) Leggere attentamente le risposte ricevute.
4) Scrivere i messaggi con il colore di default, evitare altri colori.
5) Scrivere in Italiano o in Inglese, se possibile grammaticalmente corretto, evitate stili di scrittura poco chiari, quindi nessuna abbreviazione tipo telegramma o scrittura stile SMS o CHAT.
6) Appena registrati è consigliato presentarsi nel forum dedicato.

La non osservanza delle regole porta a provvedimenti di vari tipo da parte dello staff, in particolare la non osservanza della regola 5 porta alla cancellazione del post e alla segnalazione dell'utente. In caso di recidività l'utente rischia il ban temporaneo.
Rispondi
Avatar utente
boh
Linux 4.x
Linux 4.x
Messaggi: 1027
Iscritto il: ven 16 set 2005, 0:00
Slackware: 14.2 (x64)
Kernel: 4.4.111
Desktop: KDE 4.14.32
Località: Milano
Contatta:

[C] Estrarre le cifre di un numero

Messaggio da boh »

Ciao a tutti!
Sto attualmente lavorando su un progetto per implementare l'algoritmo di exact division (Ref: Jebelean - An algorithm for exact division, pag. 4).
L'algoritmo in sè non è difficile, ma lo è di più implementarlo in modo efficiente.
In particolare, ho la necessità di estrarre iterativamente le cifre meno significative del dividendo per poter così calcolare le corrispondenti meno significative del quoziente.
Mi sto documentando sulla libreria gmp, ma non riesco a trovare nulla che riguardi il mio problema.
Vorrei evitare la soluzione classica di dividere il numero per 10 per poi scartare il decimale con l'assegnamento a integer.

Qualcuno sa darmi qualche dritta su cosa cercare? O se conosce gmp, che funzione potrebbe fare al caso mio?

P.S: anche mettere il numero in un array di caratteri non credo sia una buona soluzione, ma non ne sono certo.
"Be yourself. Everyone else is already taken." ~ Oscar Wilde

Avatar utente
masalapianta
Iper Master
Iper Master
Messaggi: 2775
Iscritto il: lun 25 lug 2005, 0:00
Nome Cognome: famoso porco
Kernel: uname -r
Desktop: awesome
Distribuzione: Debian
Località: Roma
Contatta:

Re: [C] Estrarre le cifre di un numero

Messaggio da masalapianta »

boh ha scritto:Ciao a tutti!
Sto attualmente lavorando su un progetto per implementare l'algoritmo di exact division (Ref: Jebelean - An algorithm for exact division, pag. 4).
L'algoritmo in sè non è difficile, ma lo è di più implementarlo in modo efficiente.
In particolare, ho la necessità di estrarre iterativamente le cifre meno significative del dividendo per poter così calcolare le corrispondenti meno significative del quoziente.
Mi sto documentando sulla libreria gmp, ma non riesco a trovare nulla che riguardi il mio problema.
Vorrei evitare la soluzione classica di dividere il numero per 10 per poi scartare il decimale con l'assegnamento a integer.
perchè no? in questi casi si usa proprio l'operatore modulo (se trovi qualche libreria che fa quel che chiedi, andando a vedere il sorgente scoprirai che quasi sicuramente usa questo metodo)
P.S: anche mettere il numero in un array di caratteri non credo sia una buona soluzione, ma non ne sono certo.
quindi non vuoi neanche convertire il numero in stringa (con atoi() o equivalente), smanettarlo e poi riconvertire in integer con snprintf()? allora temo che ti resti solo la bacchetta magica e poco altro.

Avatar utente
Vito
Staff
Staff
Messaggi: 4182
Iscritto il: mar 5 dic 2006, 17:28
Nome Cognome: Vito
Desktop: MacOS
Località: Monaco (DE)
Contatta:

Re: [C] Estrarre le cifre di un numero

Messaggio da Vito »

boh ha scritto: Vorrei evitare la soluzione classica di dividere il numero per 10 per poi scartare il decimale con l'assegnamento a integer.
Confesso di aver pensato subito a questa cosa non appena ho letto il titolo della discussione.
"Stat rosa pristina nomina, nomina nuda tenemus." [ Umberto Eco - Il nome della rosa]

"Faber est suae quisque fortunae ." [ Appio Claudio Cieco]

Avatar utente
brg
Linux 3.x
Linux 3.x
Messaggi: 580
Iscritto il: sab 12 mar 2011, 14:20
Slackware: 15.0
Kernel: 5.15.117
Desktop: KDE5
Località: Montecatini
Contatta:

Re: [C] Estrarre le cifre di un numero

Messaggio da brg »

L'unica alternativa che ti rimane a questo punto è implementare l'algoritmo in base 2 ed usare gli operatori logici, che probabilmente è anche la soluzione più efficace da un punto di vista computazionale. Se sei limitato alla base 10 allora divisione e resto è meglio, ma capisco che non abbia senso in un algoritmo che implementa l'operazione di divisione, quindi dovresti usare atoi (standard in C99), che però sarà sempre un passaggio più lento che usare l'operazione di divisione standard del C. Oppure ti fai la tua funzioncina in assembly, scegli tu.

Avatar utente
boh
Linux 4.x
Linux 4.x
Messaggi: 1027
Iscritto il: ven 16 set 2005, 0:00
Slackware: 14.2 (x64)
Kernel: 4.4.111
Desktop: KDE 4.14.32
Località: Milano
Contatta:

Re: [C] Estrarre le cifre di un numero

Messaggio da boh »

Grazie per le risposte!

@masalapianta: sono dubbioso sull'uso di modulo/divisione perchè sto implementando una divisione ottimizzata e farlo usando la divisione non mi sembra che abbia senso; oltretutto si parla di dividere per 10 un numero che potrebbe avere anche 100 o più cifre, non vorrei rallentasse troppo. Per l'array non l'ho escluso a priori, ma mi sembra una soluzione lenta per il fatto che il numero memorizzato nell'array va poi modificato attraverso una sottrazione e quindi dovrei riconvertirlo in numero per poi riportarlo nell'array ed estrarre la nuova ultima cifra.

@brg: in base 2 posso lavorare sui bit per estrarre il meno significativo e fare uno shift right per eliminare l'ultima, giusto? Quindi avrebbe senso prendere i due numeri in decimale, convertirli in binario, fare la divisione ottimizzata e restituire il quoziente ancora in decimale?
L'assemlby eviterei, non lo conosco molto bene 8-[
"Be yourself. Everyone else is already taken." ~ Oscar Wilde

Avatar utente
brg
Linux 3.x
Linux 3.x
Messaggi: 580
Iscritto il: sab 12 mar 2011, 14:20
Slackware: 15.0
Kernel: 5.15.117
Desktop: KDE5
Località: Montecatini
Contatta:

Re: [C] Estrarre le cifre di un numero

Messaggio da brg »

Non hai da convertire alcunché, i numeri elaborati da un calcolatore sono già tutti binari. Io farei una cosa del genere, ammesso che tu stia usando degli interi e non dei numeri in virgola mobile:

Codice: Seleziona tutto

!!!PSEUDOCODICE!!!
/* numero è la varibile da cui devi estrarre la cifra */
int numero

/* fai una copia */
int temp = numero

/* estrai l'ultima cifra binaria */
temp &= 1 

/* "dividi" per due, cioè scarti l'ultima cifra binaria*/
numero = numero >> 1

/* ora temp contiene l'ultima cifra,
 *  mentre numero è diviso per due 
 */

Puoi fare questa cosa con qualunque base che sia potenza di 2, ad es.: temp = temp & 3; numero = numero >> 2;

Avatar utente
414N
Iper Master
Iper Master
Messaggi: 2922
Iscritto il: mer 13 feb 2008, 16:19
Slackware: 15.0
Kernel: 5.15.19
Desktop: KDE5
Località: Bulagna
Contatta:

Re: [C] Estrarre le cifre di un numero

Messaggio da 414N »

boh ha scritto:[..] oltretutto si parla di dividere per 10 un numero che potrebbe avere anche 100 o più cifre, non vorrei rallentasse troppo.
Interessante... Servirebbero tra i 256 e i 512 bit per mantenere un intero da circa 100 cifre in memoria (ovviamente considerandolo senza segno, altrimenti si raddoppia).
Domanda: stai applicando questo algoritmo, prendendo come base β (radix) 10? In caso affermativo, temo tu stia commettendo un errore di fondo, in quanto l'algoritmo richiede che β sia un numero primo per garantire l'esistenza di un a' (che non sarebbe garantita in caso contrario).
Ad ogni modo, esiste anche un libreria per l'ottimizzazione delle divisioni a runtime, ovvero libdivide.

Avatar utente
boh
Linux 4.x
Linux 4.x
Messaggi: 1027
Iscritto il: ven 16 set 2005, 0:00
Slackware: 14.2 (x64)
Kernel: 4.4.111
Desktop: KDE 4.14.32
Località: Milano
Contatta:

Re: [C] Estrarre le cifre di un numero

Messaggio da boh »

Sì, l'algoritmo è quello e sì, la base deve essere prima.
Più che un errore è un'omissione, perchè se la base non è prima, l'ultima cifra del dividendo e la base devono essere coprimi per poter applicare l'algoritmo.
Attualmente sono anche propenso a cambiare progetto, perchè non trovo una possibilità di parallelizzazione senza l'uso di dispositivi hardware dedicati (systolic array).
In ogni caso, mi interessa comunque proseguire la discussione.

Libdivide potrebbe essere una buona soluzione per l'estrazione della cifra. Se la base è diversa dalla 10, i numeri è possibili inserirli comunque come se fossero decimali, anche se poi la base è diversa (es: 2555 mod 7 --> inserisco 2555 e poi l'algoritmo lo tratterà con la base specificata; dovrò comunque estrarre almeno la metà delle cifre), o sbaglio qualcosa?

@brg: la rappresentazione è binaria, ma in un numero come quello sopra io devo estrarre comunque 5 e questo non è rappresentato dall'ultima cifra binaria, o sto sbagliando qualcosa anche qui?
"Be yourself. Everyone else is already taken." ~ Oscar Wilde

Avatar utente
brg
Linux 3.x
Linux 3.x
Messaggi: 580
Iscritto il: sab 12 mar 2011, 14:20
Slackware: 15.0
Kernel: 5.15.117
Desktop: KDE5
Località: Montecatini
Contatta:

Re: [C] Estrarre le cifre di un numero

Messaggio da brg »

Allora, m'è caduta la connessione mentre stavo scrivendo un esempio, tuttavia il succo è questo: estrai 5 se la tua base è maggiore di 5, se sei in base 2 estrai 1 ed il risultato finale non cambia, hai solamente bisogno di fare un numero diverso di passaggi. Se devi ad esempio dividere 6 per 3 in base 2, fai due passaggi (K = lung(0b110) - lung(0b11) + 1 == 2), in base 8 ne fai uno solo (K = lung(06) - lung(03) + 1 == 1). Tuttavia in entrambi i casi ottieni 2 come risultato: nel primo caso 2 è 0b10 e contiene due cifre (per cui necessiti di due passaggi), mentre nel secondo caso 2 è 02 (il C identifica lo 0 iniziale come un identificatore di base 8 ) e contiene una cifra sola, che ricavi in un solo passaggio.

P.S. ho usato le notazioni binarie ed ottali per mostrare le differenze, ma usare una base non richiede di usarne la notazione. Puoi tranquillamente usare numeri in notazione decimale e implementare l'algoritmo in base 2. Tuttavia da quel che ho visto, le uniche soluzioni sensate sono quelle di usare come basi delle potenze di due. Se vuoi mi dilungo su questo punto, ma mi pare abbastanza ovvio.

Rispondi