Last active
September 16, 2025 15:04
-
-
Save MurageKibicho/39538fed9a1889f1f13eecc5f39a101b to your computer and use it in GitHub Desktop.
Using Ramanujan's Formula to find the log of a factorial
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <stdio.h> | |
| #include <stdlib.h> | |
| #include <math.h> | |
| #include <gmp.h> | |
| #include <assert.h> | |
| #include <mpfr.h> | |
| //Run: clear && gcc BirthdayAttack.c -lgmp -lm -lmpfr -o g.o && ./g.o | |
| //Complete walkthrough: https://leetarxiv.substack.com/p/birthday-attack | |
| double MPZ_Log(mpz_t x, double logarithmBase) | |
| { | |
| assert(logarithmBase != 0); | |
| if(mpz_cmp_ui(x, 0) == 0){return 0;} | |
| signed long int ex; | |
| const double di = mpz_get_d_2exp(&ex, x); | |
| return ((log(di) + log(logarithmBase) * (double) ex) / log(logarithmBase)); | |
| } | |
| double MPZ_LogFactorial(mpz_t n, double logarithmBase) | |
| { | |
| if(mpz_cmp_ui(n, 0) == 0 || mpz_cmp_ui(n, 1) == 0){return 0.0;} | |
| mpfr_prec_t prec = 256; | |
| mpfr_rnd_t rnd = MPFR_RNDN; | |
| mpfr_t nf, np1, lngamma_n, logbase_mpf; | |
| mpfr_inits2(prec, nf, np1, lngamma_n, logbase_mpf, (mpfr_ptr) 0); | |
| mpfr_set_z(nf, n, rnd); | |
| mpfr_add_ui(np1, nf, 1, rnd); | |
| mpfr_lngamma(lngamma_n, np1, rnd); | |
| mpfr_set_d(logbase_mpf, logarithmBase, rnd); | |
| mpfr_log(logbase_mpf, logbase_mpf, rnd); // log(logBase) | |
| mpfr_div(lngamma_n, lngamma_n, logbase_mpf, rnd); | |
| double result = mpfr_get_d(lngamma_n, rnd); | |
| mpfr_clears(nf, np1, lngamma_n, logbase_mpf, (mpfr_ptr) 0); | |
| return result; | |
| } | |
| double MPZ_LogProductRange(mpz_t start, mpz_t stop, double logarithmBase) | |
| { | |
| if(mpz_cmp(start, stop) > 0){return 0;} | |
| double log_b_factorial = MPZ_LogFactorial(stop, logarithmBase); | |
| mpz_sub_ui(start, start, 1); | |
| double log_a_minus_one_factorial = 0; | |
| if(mpz_cmp_ui(start, 0) >= 0) | |
| { | |
| log_a_minus_one_factorial = MPZ_LogFactorial(start, logarithmBase); | |
| } | |
| mpz_add_ui(start, start, 1); | |
| return log_b_factorial - log_a_minus_one_factorial; | |
| } | |
| // Birthday problem probability calculation | |
| double BirthdayProblem(mpz_t days, mpz_t people, double logarithmBase) | |
| { | |
| mpz_t rangeStart, rangeEnd; | |
| mpz_init(rangeStart); | |
| mpz_sub(rangeStart, days, people); | |
| mpz_add_ui(rangeStart, rangeStart, 1); // start = days - people + 1 | |
| double collisionProbability = 1.0; | |
| double log_product = MPZ_LogProductRange(rangeStart, days, logarithmBase); | |
| double log_denominator = mpz_get_d(people) * MPZ_Log(days, logarithmBase); | |
| double log_prob_no_collision = log_product - log_denominator; | |
| double prob_no_collision = pow(logarithmBase, log_prob_no_collision); | |
| collisionProbability = collisionProbability - prob_no_collision; | |
| mpz_clear(rangeStart); | |
| return collisionProbability; | |
| } | |
| int main() | |
| { | |
| mpz_t days, people; | |
| mpz_inits(days, people, NULL); | |
| mpz_set_ui(days, 365); | |
| mpz_set_ui(people, 23); | |
| double logarithmBase = 2; | |
| double result = BirthdayProblem(days, people, logarithmBase); | |
| gmp_printf("%Zd with %Zd people: %.6f\n", days, people, result); | |
| mpz_clears(days, people, NULL); | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment