Newsgroup: it.comp.lang.c
Titolo: Sondaggio: moltiplicazione

Come scrivereste, in C, una funzione che esegua la moltiplicazione tra 
due valori (non prefissati) in [0,255] potendo usare l'operatore 
incremento, ma non gli operatori somma, sottrazione, moltiplicazione, 
divisione, né gli operatori sui bit e senza chiamare altre funzioni?
Kiuhnm


int Kiuhnm1(int a, int b)
{
   if (a==0 && b==0) return 0;
   else
   if (a==0 && b==1) return 0;
   ....
   else if (a==255 && b==255) return 65025;
   else return 666666;
}
int Kiuhnm2(int a, int b)
{
   int i,j,s=0;
   for (i=0; i<a; i++)
   for (j=0; j<b; j++) s++;
   return s;
}
ciao,
g.


sarà brutale ma funge :)
#include <stdio.h>
#include <stdlib.h>
int mul(int x, int y) {
    int i,j,k;
    k=((x>y)?y:x);
    for(i=0;i<x;i++)
       for(j=1;j<y;j++)
         k++;
    return k;
}
int main(int argc, char **argv) {
    int x,y;
    scanf("%d\n",&x);
    scanf("%d",&y);
    printf("%d\n",mul(x,y));
    return 0;
}
ciao.

 }
  Veramente non funge affatto. L'istruzione :
  k=((x>y)?y:x);
oltre che inutile e' concettualmente sbagliata.
Prova a moltiplicare prima 2 x 4 e poi 4 x 2 ...
e confronta i risultati...
ciao,
g.


wrote:

#include <stdio.h>
#include <stdlib.h>
unsigned int M[256][256]={0};
int init()
{
    unsigned char x, y;
    for (x=0; x<255; x++)
      for (y=0; y<255; y++) 
        M[x][y] = x*y;
}
int mul(unsigned char x, unsigned char y)
{
    return M[x][y];
}
int main()
{
    int i;  
 
    init();
 
    for (i=0; i<9; i++) {
      unsigned char x = rand()%256, y=rand()%256;
      printf("%d x %d = %d\n", x, y, mul(x,y));
    }
    return 0;
}

 unsigned int M[256][256]={0};
Del resto ho limitato il range dei valori proprio per permettere anche 
questa soluzione.
Kiuhnm

 e confronta i risultati...
oops! doveva essere questo:
int mul(int x, int y) {
    int i,j,k;
    (x>y) ? (k=y,y=x,x=k) : (k=x) ;
    for(i=0;i<x;i++)
       for(j=1;j<y;j++)
         k++;
    return k;
}
un'"ottimizzazione" stupidissima per evitare 
un'iterazione... sono un po' fuso :)
ciao.

Kiuhnm ha scritto:

Nessuno offre di più?
Se volete posto la mia soluzione.
Kiuhnm


"di piu'" rispetto a quale parametro ?
non era ben chiaro se le risposte dovevano
essere ottimizzate rispetto a qualcosa
(numero istruzioni, tempo di calcolo, etc.)
o se volevi solo vedere diversi approcci.
comunque posta pure la tua soluzione.
ciao,
g.

 "di piu'" rispetto a quale parametro ?
Rispetto alla varietà. Per ora ho visto praticamente 3 approcci (più una 
leggera variazione scritta da cane :) ). Magari qualcuno verrà fuori con 
qualcosa di diverso e inaspettato. Aspetto ancora qualche oretta prima 
di postare.
Del resto non tutti leggono il ng assiduamente come noi.
Kiuhnm

 Aspetto ancora qualche oretta prima di postare.
Hai qualcosa nella manica di cosě sensazionale da meritare un'attesa del
genere? ... 
-- 
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it

 genere? ... 
Be', per me è carina.
Kiuhnm

, è una spamtrap
Usate zello <at> despammed <dot> com

Kiuhnm ha scritto:

Uso una chiamata a funzione solo per rendere il codice più leggibile.
Spero inoltre che il codice sia C puro e non C++.
typedef union _multiPtr
{
	int s;
	char (*s1)[2];
	char (*s2)[4];
	char (*s3)[8];
	char (*s4)[16];
	char (*s5)[32];
	char (*s6)[64];
	char (*s7)[128];
	char (*s8)[256];
	char (*s9)[512];
	char (*s10)[1024];
	char (*s11)[2048];
	char (*s12)[4096];
	char (*s13)[8192];
	char (*s14)[16384];
	char (*s15)[32768];
	char (*s16)[65536];
} multiPtr;
int add(int a, int b)
{
	multiPtr s, tmp, lastTmp;
	s.s = a;
	lastTmp.s = tmp.s = 0;
	tmp.s16++;
	if (tmp.s <= b)
	{
		s.s16++;
		lastTmp = tmp;
	}
	tmp = lastTmp;
	tmp.s15++;
	if (tmp.s <= b)
	{
		s.s15++;
		lastTmp = tmp;
	}
	tmp = lastTmp;
	tmp.s14++;
	if (tmp.s <= b)
	{
		s.s14++;
		lastTmp = tmp;
	}
	tmp = lastTmp;
	tmp.s13++;
	if (tmp.s <= b)
	{
		s.s13++;
		lastTmp = tmp;
	}
	tmp = lastTmp;
	tmp.s12++;
	if (tmp.s <= b)
	{
		s.s12++;
		lastTmp = tmp;
	}
	tmp = lastTmp;
	tmp.s11++;
	if (tmp.s <= b)
	{
		s.s11++;
		lastTmp = tmp;
	}
	tmp = lastTmp;
	tmp.s10++;
	if (tmp.s <= b)
	{
		s.s10++;
		lastTmp = tmp;
	}
	tmp = lastTmp;
	tmp.s9++;
	if (tmp.s <= b)
	{
		s.s9++;
		lastTmp = tmp;
	}
	tmp = lastTmp;
	tmp.s8++;
	if (tmp.s <= b)
	{
		s.s8++;
		lastTmp = tmp;
	}
	tmp = lastTmp;
	tmp.s7++;
	if (tmp.s <= b)
	{
		s.s7++;
		lastTmp = tmp;
	}
	tmp = lastTmp;
	tmp.s6++;
	if (tmp.s <= b)
	{
		s.s6++;
		lastTmp = tmp;
	}
	tmp = lastTmp;
	tmp.s5++;
	if (tmp.s <= b)
	{
		s.s5++;
		lastTmp = tmp;
	}
	tmp = lastTmp;
	tmp.s4++;
	if (tmp.s <= b)
	{
		s.s4++;
		lastTmp = tmp;
	}
	tmp = lastTmp;
	tmp.s3++;
	if (tmp.s <= b)
	{
		s.s3++;
		lastTmp = tmp;
	}
	tmp = lastTmp;
	tmp.s2++;
	if (tmp.s <= b)
	{
		s.s2++;
		lastTmp = tmp;
	}
	tmp = lastTmp;
	tmp.s1++;
	if (tmp.s <= b)
	{
		s.s1++;
		lastTmp = tmp;
	}
	tmp = lastTmp;
	tmp.s++;
	if (tmp.s <= b)
	{
		s.s++;
		lastTmp = tmp;
	}
	return s.s;
}
int mul(int a, int b)
{
	int _1a = add(a, a);
	int _2a = add(_1a, _1a);
	int _3a = add(_2a, _2a);
	int _4a = add(_3a, _3a);
	int _5a = add(_4a, _4a);
	int _6a = add(_5a, _5a);
	int _7a = add(_6a, _6a);
	int _8a = add(_7a, _7a);
	multiPtr s, tmp, lastTmp;
	s.s = lastTmp.s = tmp.s = 0;
	tmp.s8++;
	if (tmp.s <= b)
	{
		s.s = add(s.s, _8a);
		lastTmp = tmp;
	}
	tmp = lastTmp;
	tmp.s7++;
	if (tmp.s <= b)
	{
		s.s = add(s.s, _7a);
		lastTmp = tmp;
	}
	tmp = lastTmp;
	tmp.s6++;
	if (tmp.s <= b)
	{
		s.s = add(s.s, _6a);
		lastTmp = tmp;
	}
	tmp = lastTmp;
	tmp.s5++;
	if (tmp.s <= b)
	{
		s.s = add(s.s, _5a);
		lastTmp = tmp;
	}
	tmp = lastTmp;
	tmp.s4++;
	if (tmp.s <= b)
	{
		s.s = add(s.s, _4a);
		lastTmp = tmp;
	}
	tmp = lastTmp;
	tmp.s3++;
	if (tmp.s <= b)
	{
		s.s = add(s.s, _3a);
		lastTmp = tmp;
	}
	tmp = lastTmp;
	tmp.s2++;
	if (tmp.s <= b)
	{
		s.s = add(s.s, _2a);
		lastTmp = tmp;
	}
	tmp = lastTmp;
	tmp.s1++;
	if (tmp.s <= b)
	{
		s.s = add(s.s, _1a);
		lastTmp = tmp;
	}
	tmp = lastTmp;
	tmp.s++;
	if (tmp.s <= b)
	{
		s.s = add(s.s, a);
		lastTmp = tmp;
	}
	return s.s;
}
Kiuhnm

         return (y?x+sum(x,--y):0);
L'operatore + non è consentito!
Kiuhnm

 L'operatore + non è consentito!
e definisci pure quello ricorsivamente :)
x+y=succ(x)+(y-1)
-- 
Firma in costruzione

 Uso una chiamata a funzione solo per rendere il codice più leggibile.
Oltre ad essere un obbrobbrio, è meno efficiente della mia ;-P


 Uso una chiamata a funzione solo per rendere il codice più leggibile.
KISS va a farsi benedire

     char (*s16)[65536];
Ci si potrebbe anche fermare a s15, in realtà.
Kiuhnm

  M[x][y] = x*y;
Però così è sleale. :)
Io invece ho preparato un programmino che svolge il compito richiesto senza 
nemmeno usare l'operatore incremento.
 
http://cassandra.comm2000.it/~maxim/pub/mul.c.txt
E' un po' lunghetto. :-)
Max

 Max
Mi ricordi un tizio che per una compagnia di assicurazioni ha scritto in 
Java una classe con 1024 metodi per gestire le combinazioni do 10 
clausole differenti.  :-)
LP

 >> E' un po' lunghetto. :-)
Non c'era bisogno che la scrivessi tutta!
Kiuhnm

Chiedo scusa, ho quotato male :(
Kiuhnm

Kiuhnm wrote:

Uh? Non crederai mica che l'abbia *scritta*? 
Max

 Uh? Non crederai mica che l'abbia *scritta*? 
Non l'hai scritta tutta a mano e poi acquisita con lo scanner?
Kiuhnm


In verità l'ho fatta scrivere al mio nipotino. Ci teneva tanto.
Max

Però così è sleale. :)
No no! :-) ... trattasi di semplice precalcolo.  Si fa anche con
seno/coseno per velocizzare le operazioni grafiche ;-)
In realtà, la moltiplicazione in sé, non fa nulla di illegale e se mi
dimostrate di fare qualcosa di più efficiente vi pago una cena ;-)

 dimostrate di fare qualcosa di più efficiente vi pago una cena ;-)
E' più efficiente inserire nel codice sorgente la tavola già pronta.
Kiuhnm

E' più efficiente inserire nel codice sorgente la tavola già pronta.
E', in sostanza, ciò che faccio io.  Il fatto che il compito di
inizializzare la tavola sia affidato a una funzione, non vuol dire
nulla.  Scrivi un sorgente che prepara l'array scrivendolo su un file
di testo, copia&incolla l'array nel codice e hai fatto.
E' solo per pigrizia che non l'ho fatto io.  In quanto alla
moltiplicazione, non c'è nulla di più efficiente.

 moltiplicazione, non c'è nulla di più efficiente.
Vorrai dire in quanto a moltiplicazione *di valori in [0,255]*!
Il mio è l'unico logaritmico sia per memoria (O(logn)) che per tempo 
(O((logn)^2).
Kiuhnm

Vorrai dire in quanto a moltiplicazione *di valori in [0,255]*!
Esatto.  Cioè ciò che tu richiedevi.

 In verità l'ho fatta scrivere al mio nipotino. Ci teneva tanto.
E... questo si chiama nonnismo :)
Kiuhnm