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

Pages: 1-4041-

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.

Name: Anonymous 2012-09-25 22:37

>>40
I thought so. Come up with a real answer next time instead of just giving some bullshit guess.

Name: Anonymous 2012-09-25 23:38

factorial n = product [1..n]

Name: Anonymous 2012-09-26 3:28

>>2
I like how LISPers love to abuse recursion all the time claiming it makes their code more elegant, but the C version is faster, easier read, and more elegant.

Go fuck yourself LISPers. C is better than your shitty language

Name: Anonymous 2012-09-26 3:38

>>43

many c compilers support tail call optimization. The only thing preventing you from getting just as lispy with c is how some statements are hard to make into expressions. Tail call style is more expressive than loops, and can actually end up compiling to faster code, since the equivalent with loops can be a mess with indicator variables. But nevermind. You'll never understand. Go back to scrubbing your toilet bowlhard to find bug buried within the quadruple nested loop caused by a state variable that was initialized 20 lines down to a value that would have made sense if this condition wasn't triggered during this test case as well.

Name: Anonymous 2012-09-26 3:47

>>44
Except that what you said was the point. LISP fanboys make it seem as though LISP is this ultra powerful language that can use recursion to elegantly provide solutions when in reality, it can be done in C, and often better.

Name: Anonymous 2012-09-26 4:12

>>45

nested functions help, and these are not in the c standard. Tail recursion in c is also not guaranteed to work, so it is not portable. Actual closures that can escape the function body of their declaration are nice too. It is possible to get close to these features in standard C, but you don't have the same convenience or security. If you like these features but don't like scheme (I'm not sure why you have such a dislike of scheme, you seemed to say that it was overrated but the only thing you mentioned was its association with recursion, and by that I can only assume you mean tail recursive style (and by a tail recursive lisp, I can only assume you meant (scheme))), you might want to check out ML.

Name: Anonymous 2012-09-26 4:15

>>45
C
U MENA JAVASCRIPT

Name: Anonymous 2012-09-26 4:15

>>45

and when people talk about lisp being powerful, they are usually referring to its macro system.

Name: Anonymous 2012-09-26 4:51

>>48
Lisp has no macro system. Did you mean CL or Scheme? They are very different to each other.

Name: Anonymous 2012-09-26 5:24

>>49
scheme's macro system is advanced, but it can still all be implemented using lisp's defmacro.
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 -