Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

Racket

Name: Anonymous 2012-09-25 13:28

there must be a better way to do this right


(define (factorial n)
    (define (iter n result)
        (if (= n 0)
            result
            (iter (- n 1) (* result n))))
    (iter n 1))

Name: Anonymous 2012-09-25 13:31

int factorial (int n) {
  return n ? n * factorial(n-1) : 1;
}

GCC performs TCO on this if you let it optimize.

Name: Anonymous 2012-09-25 14:12


(let loop ((n n) (result 1))
  (if (= n 0) result
    (loop (- n 1) (* result n))))

Name: Anonymous 2012-09-25 16:40

factorial n = n * factorial (n - 1)
factorial 0 = 1

Name: Anonymous 2012-09-25 16:43

>>2
factorial(-1);
STACK OVERFLOW

Name: Anonymous 2012-09-25 17:02

Depends, that is the very standard way of doing the iterative factorial function. The other standard method is recursive:

(define (factorial n)
   (if (< n 2)
        1
       (n * (factorial (- n 1)))))

If you're a dick, there's equivalent forms in message passing style, continuation passing style, the Y-recombinator version, and if your maximum autism SKI church numeral style.

Name: Anonymous 2012-09-25 17:06

>>5
You'd get that with unsigned ints anyway.

Name: Anonymous 2012-09-25 17:07

>>5
There is no stack in the C programming language, read the standard newfriend.

Name: Anonymous 2012-09-25 17:16

>>8
[citation needed]

Name: Anonymous 2012-09-25 17:19

>>9
It's not part of the standard. It's just a method of implementing C.

Name: Anonymous 2012-09-25 17:33

>>9
ISO/IEC 9899:2011
http://iso-9899.info/wiki/The_Standard

>>1
There is a better way to do it.

primePowerOf :: Integer -> Integer -> Integer
primePowerOf n p = (n - s p n) `div` (p - 1)
  where s p 0 = 0
        s p n = let (q,r) = n `divMod` p in s p q + r

factorisedFactorial :: Integer -> [(Integer,Integer)]
factorisedFactorial n = parMap rseq (ap (,) $ primePowerOf n) $ takeWhile (<= n) primes

factorial :: Integer -> Integer
factorial = product . parMap rseq (uncurry (^)) . factorisedFactorial

Name: Anonymous 2012-09-25 17:37

>>9
He's right. He's also a complete shithead if he can't name a single x86 targeting C compiler in modern use that doesn't use stacks.

Name: Anonymous 2012-09-25 17:41

x86
ISHYGDDT

Name: Anonymous 2012-09-25 17:44

>>13
ISHYDIAF

Name: Anonymous 2012-09-25 17:46

>>12
What are local variables using as memory then faggot?

Name: Anonymous 2012-09-25 17:48

I don't understand why you guys are bothering to discuss this, it's just an implementation detail that has nothing to do with C itself and is completely unrelated to >>2.

>>15
Well in a regular x86 implementation you could use the heap if you wanted to, even for local variables, the compiler could just insert malloc and free where it needed to.

Name: Anonymous 2012-09-25 17:53

I always laughed when sussman claimed doing what OP did was an itetative approach when it's clearly slow ass recursion

Name: Anonymous 2012-09-25 17:55

>>15
Registers.

Name: Anonymous 2012-09-25 17:56

>>12
what do you mean he's right? The shit that code gets compiled into uses the stack. is the generated machine code and the x86  asm shit one in the same logically?

Name: Anonymous 2012-09-25 17:57

>>18
And what happens when i have 100 local variables?

Name: Anonymous 2012-09-25 18:00

>>20
Get an Intel Itanium.

Name: Anonymous 2012-09-25 18:02

>>19
There's a lot more architectures than just shitty x86.

>>20
The compiler says ``Fuck you."
except on IA-64, where it just uses 100 of the 128 registers.

Name: Anonymous 2012-09-25 18:06

>>18
Even with an Itanium I don't see how registers alone could be used to create a C implementation, a conforming implementation must be able to handle at least 511 identifiers with block scope declared in one block and be able to handle at least 127 nesting levels of blocks, that's a lot of registers, especially when a single object can consist of 65535 bytes (hosted environment only).

Name: Anonymous 2012-09-25 18:10

>>5
Now that we are talking about implementation details I would like to bring notice that the function would not produce a stack overflow when compiled with GCC and optimization on x86, the call instruction is nowhere to be found in the resulting object code it only uses jmp.

Name: Anonymous 2012-09-25 18:12

>>24
Here is the disassembly of the object file from my machine.

00000000 <factorial>:
   0:   8b 54 24 04             mov    edx,DWORD PTR [esp+0x4]
   4:   b8 01 00 00 00          mov    eax,0x1
   9:   85 d2                   test   edx,edx
   b:   74 0b                   je     18 <factorial+0x18>
   d:   8d 76 00                lea    esi,[esi+0x0]
  10:   0f af c2                imul   eax,edx
  13:   83 ea 01                sub    edx,0x1
  16:   75 f8                   jne    10 <factorial+0x10>
  18:   f3 c3                   repz ret

Name: Anonymous 2012-09-25 18:30

>>19
I don't think you understand what's going on here. That's what your compiler does. That's what my compiler does. It is not what every compiler in the set of all conforming C compilers do.

>>24-25
Ty.

Name: Anonymous 2012-09-25 18:56

>>25
repz ret
Huh?

Name: Anonymous 2012-09-25 19:09

>>26
Are you saying some C compilers don't use the stack, or that its just not necessary? Where the fuck does it keep the thread environment? I suppose C itself isn't really reliant on the stack, which I suppose would explain why you can't access the stack from C.

>>17
I was using the SCIP definition, regarding how frames work with it. http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1

Scheme uses arcane magic to tail-optimize the function, making it essentially iterative

Name: Anonymous 2012-09-25 19:28

>>28
If you think that's arcane magic, just wait til you see the rest!

Name: Anonymous 2012-09-25 19:38

>>29
lel
The best part of scheme is when you can use an infinite list of accelerators to accelerate the convergence of the previous element, where the first element is an infinite list of a converging series.

Name: Anonymous 2012-09-25 19:42

>>3

wow named let expressions are nice
here it is now with it:


;; factorial using a named let expression
(define (fact n)
    (let loop ((n n) (result 1))
        (if (= n 0) result
        (loop (- n 1) (* result n)))))

Name: Anonymous 2012-09-25 20:03

>>28
Are you saying some C compilers don't use the stack, or that its just not necessary?
As long as we're not talking of extant ones, sure. Otherwise that's not what I'm saying.

Where the fuck does it keep the thread environment?
Wherever it wants. It's implementation defined. You've already been given an example. Think up your own!

I suppose C itself isn't really reliant on the stack
Holy fuck. How many times have you been told this very thing just now?

Name: Anonymous 2012-09-25 20:19


int main(void) {
  int a = 1,b = 2,c = 3,d = 4,e = 5,f = 6,g = 7;
  return 0;
}
$ gcc -O0 -S fagstorm.c
$ cat fagstorm.s
.globl main
        .type   main, @function
main:
.LFB2:
        pushq   %rbp
.LCFI0:
        movq    %rsp, %rbp
.LCFI1:
        movl    $1, -4(%rbp)
        movl    $2, -8(%rbp)
        movl    $3, -12(%rbp)
        movl    $4, -16(%rbp)
        movl    $5, -20(%rbp)
        movl    $6, -24(%rbp)
        movl    $7, -28(%rbp)
        movl    $0, %eax
        leave
        ret
.LFE2:
        .size   main, .-main
        .section        .eh_frame,"a",@progbits
.
.
.

rbp

Name: Anonymous 2012-09-25 20:20


int main(void) {
  int a = 1,b = 2,c = 3,d = 4,e = 5,f = 6,g = 7;
  return 0;
}
$ gcc -O0 -S fagstorm.c
$ cat fagstorm.s
.globl main
        .type   main, @function
main:
.LFB2:
        pushq   %rbp
.LCFI0:
        movq    %rsp, %rbp
.LCFI1:
        movl    $1, -4(%rbp)
        movl    $2, -8(%rbp)
        movl    $3, -12(%rbp)
        movl    $4, -16(%rbp)
        movl    $5, -20(%rbp)
        movl    $6, -24(%rbp)
        movl    $7, -28(%rbp)
        movl    $0, %eax
        leave
        ret
.LFE2:
        .size   main, .-main
        .section        .eh_frame,"a",@progbits
.
.
.

rbp

Name: Anonymous 2012-09-25 20:24

Now, find n such that n is greater than 150209 and n! + 1 is prime.

Name: Anonymous 2012-09-25 21:37

>>35
17629025516.

Name: Anonymous 2012-09-25 22:09

>>32
Not many considering some of those times were in that post. Sorry I couldnt jmp back into the the conversation mid reply

Name: Anonymous 2012-09-25 22:21

>>36
Can you prove it?

Name: Anonymous 2012-09-25 22:22

>>37
Prior to that you were told 5 times that it isn't part of the spec, 3 of those times it was explained that it isn't necessary for implementation (because *it's not part of the spec*)

Name: Anonymous 2012-09-25 22:33

>>38
I have discovered a truly marvelous proof of it, which this post is too small to contain.
Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List
All trademarks and copyrights on this site are owned by their respective parties. All comments and posts are the responsibility of their own posters.
- Tinychan + 2ch Mode -