Well, someone wrote that they could write a program to do 1000! in one line of Haskell. I said that it would take less than 100 lines of C to do the same. I wrote the program, and it is less than 100 lines of C:
#include <stdio.h>
#include <string.h>
#define LENGTH 10000
int max (int a, int b) { return (a > b) ? a : b; }
int min (int a, int b) { return (b > a) ? a : b; }
int length (unsigned char * a)
{
int i;
i = LENGTH - 1;
while ((a[i] == 0) && (i >= 0)) i--;
return i + 1;
}
void add (unsigned char * a, unsigned char * b)
{
int i, c, C;
c = min(max(length(a), length(b)) + 1, LENGTH);
for (i = 0, C = 0; i < c; i++)
{
a[i] += b[i] + C;
C = a[i] > 99;
if (C) a[i] -= 100;
}
}
unsigned char x [LENGTH], y [LENGTH];
void mul (unsigned char * a, unsigned char * b)
{
int i, j, c, d, C;
memset(y, '\0', LENGTH);
c = min(length(a) + length(b) + 1, LENGTH);
d = length(b);
for (i = 0; i < d; i++)
{
memset(x, '\0', LENGTH);
for (j = 0, C = 0; (i + j) < c; j++)
{
x[i + j] = (a[j] * b[i] + C) % 100;
C = (a[j] * b[i] + C) / 100;
}
add(y, x);
}
memcpy(a, y, LENGTH);
}
void numset (unsigned char * a, unsigned long b)
{
int i;
for (i = 0; i < LENGTH; i++)
{
a[i] = b % 100;
b /= 100;
}
}
int tz (unsigned char * a)
{
int i;
for (i = 0; i < LENGTH; i++) if (a[i] != 0) return 0;
return 1;
}
unsigned char arg_res [LENGTH];
int main (void)
{
unsigned long a;
int i;
memset (minus1, 99, LENGTH);
printf("Input the number to take the factorial of: ");
scanf("%lu", &a);
numset(arg_res, a);
fact(arg_res);
i = LENGTH - 1;
while (arg_res[i] == 0) i--;
while (i >= 0)
{
printf("%02d", (int) arg_res[i]);
i--;
}
putchar('\n');
return 0;
}
>>120
As >>123 pointed out, the problem isn't that it's slow. The problem is that it wastes processor time that could be used for other tasks, or energy that could be saved by not running the processor (or running it at a slower clock speed while idle).
Name:
Anonymous2012-07-18 23:59
>>123 >>124
then work a bit more and earn those extra pennies in less than 15 seconds
you're not going to die for working 5 seconds more
and stop using x86
Name:
Anonymous2012-07-19 0:12
>>125
The Lemote 8133 is not yet out, I will keep using x86.
>>125
I bet you're one of those assholes who say that 5 miles per gallon ought to be good enough for anybody. Wasting electricity means wasting fossil fuels, and no amount of work will appreciably change the amount of fossil fuels available on Earth.
Name:
Anonymous2012-07-19 3:14
>>127
My entire household is powered by wind and sun power. Checkmate, faggot.
Who Gives a fuck about faktorial i want GAMMA FUNCKTION IMPLENMENTANTION RITE NAO!!!!!!!!!!!!!
IVE BEEN TRYING FOR MONTSH TO FIGURE OUT HOW GAMMA FUNCTIONdsagdBAUIDHBADSikhjui!? AND MY NEURAL NETS DONT CONVERGE FUCK THIS SHIT
OH WAIT MY COMPILER HA S BULILT IN LIBRARY TO DO LOG_GAMMA BUT I HAVE no CLUE HOW the HELL IT DOES IT SO EXPLAIN ME THE STEPS IN GETTING THE GAMMA FUNCTION OR MAYBE POSSIBLEY EVEN AN ASM CODE SNIPPET SOR SOMETHING INSANELY CRazy LIKE TGAt LOL!!
IF YOU DONT GOING TO DO PUT CODE HERE I WILL ANALYZE THE CODE MYSELF!!!!!!!!!!!!!!!!!!!!!!! BUT THATS HRARD TO DO!!!!!!!! THEREFORE U MUST POST HERE CODE OR I WIL BE BUTTTTTTT ANGREY!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!~~~
Name:
Anonymous2012-07-20 17:59
product([], 1).
product([H|T], X) :- product(T, Y), X is H * Y.
factorial(N, R) :- numlist(2, N, Ns), product(Ns, R).
Name:
Anonymous2012-07-20 22:55
>>142
This is unnecessarily memory inefficient, not tail-recursive, only works one way and it also does not conform to ISO-Prolog.
successor(X, Y) :-
number(Y) -> X is dec(Y); number(X) -> Y is inc(X);
throw(error(instantiation_error, successor/2)).
nonnegative(0).
nonnegative(N) :-
number(N) -> N > 0;
nonnegative(M), N is M + 1.
factorial(0, R, R) :- !.
factorial(N, P, R) :-
successor(M, N), A is N * R, factorial(M, P, A).
factorial(N, R) :-
nonnegative(N), factorial(N, R, 1).
Whether the query
?- factorial(100, N).
actually yields the correct number also depends on the implementations limitations when it comes to integers.
Name:
Anonymous2012-07-21 1:22
>>143
WTF does that even do? I know it squares a number, but how?
Name:
Anonymous2012-07-21 1:34
>>144
It does in fact not square any number unless you are referring to the number 1, but that is indeed the only number it will square.
As for how it is done, that is just a silly implementation detail.
>>146
Are you referring to the squaring of the number 1? Then no, it is a consequence of both 0! and 1! being 1.
Name:
Anonymous2012-07-21 1:41
2976579765 in decimal hurr
Name:
Anonymous2012-07-21 2:21
>>143
If you're going to bitch about inefficiency, you really should do it right.
product([], 1).
product([H|T], X) :- product(T, Y), X is H * Y.
sieve(N, [2|PS]) :- % PS is list of odd primes up to N
retractall(mult(_)),
sieve_O(3,N,PS).
sieve_O(I,N,PS) :- % sieve odds from I up to N to get PS
I =< N, !, I1 is I+2,
( mult(I) -> sieve_O(I1,N,PS)
; ( I =< N / I ->
ISq is I*I, DI is 2*I, add_mults(DI,ISq,N)
; true ),
PS = [I|T],
sieve_O(I1,N,T)
).
sieve_O(I,N,[]) :- I > N.
add_mults(DI,I,N) :-
I =< N, !,
( mult(I) -> true ; assert(mult(I)) ),
I1 is I+DI,
add_mults(DI,I1,N).
add_mults(_,I,N) :- I > N.
prime_power_of_s(_, 0, A, S) :- S is A.
prime_power_of_s(P, N, A, S) :- Q is div(N, P), R is mod(N, P), B is A + R, prime_power_of_s(P, Q, B, S).
prime_power_of(N, P, R) :- prime_power_of_s(P, N, 0, S), R is div(N - S, P - 1).
>>149
the fugliness of your code is only matched by its author's.
Name:
Anonymous2012-07-21 3:02
>>150
Your shitty (GNU?) implementation is showing. >>149 is tail recursive, much faster than >>143, and uses much less memory. Also, on a decent implementation, >>142 is only slower than >>143 by a small constant factor, and uses a about the same amount of memory.
Name:
Anonymous2012-07-21 3:05
>>152
And yet it doesn't even manage to answer the simple query
>>157
Yes evaluated arithmetic doesn't work both ways, so you have to actually think.
Name:
Anonymous2012-07-21 18:35
>>158
I'm pretty sure that was >>157's point, in response to >>156's irrational belief that Prolog should make thinking on his part unnecessary.
Name:
Anonymous2012-07-21 19:33
>>159
Nope that's not what I said. I said that you should design rules that work both ways, since it's Prolog and end users kind of expect usability.
There is a golden middle road here, where ISO-Prolog implementations can easily figure out what you're trying to do while also making the solution efficient, in any case the most stable and usable implementation never looks like >>142 or >>149.