this post was submitted on 30 Nov 2024
10 points (100.0% liked)

Programming

241 readers
8 users here now

Welcome to the Lemmygrad programming community! This is a space where programmers of all levels can discuss programming, ask for help with problems, and share their personal programming projects with others.


Rules

  1. Respect all users, regardless of their level of knowledge in programming. We're here to learn and help each other improve.
  2. Keep posts relevant to programming and related topics.
  3. Respect people's personal preferences. If you disagree with someone's choice of programming language, method of formatting code, or anything else, don't attack the poster. Genuine criticism is fine, but personal attacks are not.
  4. In order to promote breaks from typing, all code snippets must be photos of code written on paper.
    Just kidding :), please use proper markdown code blocks.

founded 2 years ago
MODERATORS
you are viewing a single comment's thread
view the rest of the comments
[–] [email protected] 4 points 3 weeks ago* (last edited 3 weeks ago) (3 children)

Real talk, Lisp is the fucking GOAT. The only time I've ever been flabbergasted by a program was while learning Lisp, and seeing just how disgustingly efficient it is with recursive algorithms such as Fibonacci. Like, it was limited only by how much ram was available. It seriously had no problem finding the millionth Fibonacci number. Like, what? Write that in C or Fortran and try finding the 34th Fibonacci number.

[–] [email protected] 4 points 3 weeks ago* (last edited 3 weeks ago) (1 children)

Finding Fibonacci numbers in C is easy, even when using recursion. Here is a program that can find the 1,000,000th Fibonacci number. It's too big to paste the output of the program here but here you can find it on pastebin here.

#include <stdio.h>
#include <gmp.h>

void fib(int idx, mpz_t *a, mpz_t *b, mpz_t *c)
{
	mpz_add(*c, *a, *b);
	mpz_set(*a, *b);
	mpz_set(*b, *c);
	if (idx < 0) return;
	fib(idx - 1, a, b, c);
}

int main()
{
	mpz_t a; mpz_init(a);
	mpz_t b; mpz_init(b);
	mpz_t c; mpz_init(c);
	mpz_set_str(a, "1", 10);
	mpz_set_str(b, "0", 10);

	fib(1000000, &a, &b, &c);
	mpz_out_str(stdout, 10, c);
	printf("\n");
	
	mpz_clear(a);
	mpz_clear(b);
	mpz_clear(c);
	return 0;
}

You need to compile with the -O2 flag in GCC. If your recursive call is at the end of the function, this is called tail recursion, and when using that flag, the GCC compiler is smart enough to not allocate more memory on the stack every time it does a recursive call, so you don't run out of memory.

[–] [email protected] 2 points 3 weeks ago* (last edited 3 weeks ago)

Yes, if you use gmp.h, you can do it. Lisp does it out of the box. The problem isn't tail recursion (although that's a great way of saving memory), it's that the size of an integer in a normal language is 64 bits at the maximum. If you have a library such as GMP to coerce that into an array underneath, then it can be done.

load more comments (1 replies)