Hello,
To calculate the formula n!/(n-r)!, I wrote the following program:
function combinations(n, r)
n = BigInt(factorial(n))
r = BigInt(factorial(r))
t = BigInt(factorial(n-r))
final = BigInt(n / (t * r))
return final
end
function start()
print("Please enter N: ")
n = parse(Int, readline())
print("Please enter R: ")
r = parse(Int, readline())
println(combinations(n, r))
end
start()
Maybe at this point it’s time to think why you are writing this function.
If that’s just to practice reusing your previous results, this implementation is fine.
If that’s to get an idea how things are done in practice, you need to think of how you can simplify the problem. In this implementation, you do enormous calculations to get C_n^n, which is totally redundant, as we know it’s 1.
The things to notice are:
C^n_k = C^n_{n-k}. Using this, you can always transform your calculations so that r \ge n / 2.
n! / r! = (r+1)(r+2)\dots n, so that it makes sense to make a specialized function for that operation.
In the end, it might be:
function combinations(n::Integer, r::Integer)
p = max(r, n - r)
# (p+1)(p+2)...n - implementation is left as an exercise
numer = factorial_ratio(n, p)
denom = factorial(n - p)
return div(numer, denom)
end
In general, stop sharing programs with readline inputs because a function call with inputs written into source code is much clearer to us and we can’t guess what you’re typing. You should also generally share an error’s stacktrace so we have some idea where it’s happening.
In this specific case however, it’s more apparent where things are going wrong. We know that the combination formula should always have an integer value, ignoring overflow issues. InexactErrors happen when you try to convert non-integer values to integer types. Let’s see what you’re computing:
function combinations(n, r)
n = BigInt(factorial(n)) # n!
r = BigInt(factorial(r)) # r!
t = BigInt(factorial(n-r))# (n!-r!)!
final = BigInt(n / (t * r)) # n!/ ((n!-r!)! * r!)
return final
end
Reusing variable names ruined the formula, you are neither calculating the permutation formula n!/(n-r)! in your title nor the combination formula n!/(r!(n-r)!) in your actual code. Trailing ! are legal in variable names:
julia> function combinations2(n, r)
n! = BigInt(factorial(n)) # n!
r! = BigInt(factorial(r)) # r!
n_r! = BigInt(factorial(n-r))# (n-r)!
final = BigInt(n! / (n_r! * r!)) # n!/ ((n-r)! * r!)
final
end
combinations2 (generic function with 1 method)
julia> combinations2(4, 3)
4
But I don’t like that much because n_r! was very easy to mistype as n-r! and that mistake is only caught at runtime.
The less immediate issue is that your type conversions are misguided (combinations2 does not fix this). If you want to deal with big integers, n and r need to be BigInt to begin with. There’s no point in erroring on factorial(21) before attempting to convert to BigInt. Dividing 2 BigInts is also problematic because it makes a BigFloat, which is designed to have a limited but adjustable precision. If you don’t fix any possible precision losses from that, converting to BigInt afterward won’t help. Since n!/r! or n!/(n-r)! is a product of a sequence of integers, try to pick the prod call to minimize intermediate values.
function combinations(n, r)
n = BigInt(factorial(n))
r = BigInt(factorial(r))
v = BigInt(n - r)
t = BigInt(factorial(v))
final = BigInt(n / (t * r))
return final
end
I got the following error:
Please enter N: 4
Please enter R: 3
ERROR: LoadError: InexactError: BigInt(6.247682787434490584886545740022933369407761633787846742164271645199818938450171e-16)
Thanks for providing the readline inputs for clarity, but you should share the other lines in the error’s stacktrace for clarity as well. That aside, you’re running into the same error because you didn’t fix the reusage of variable names that ruined the formula.
function combinations(n, r)
x = BigInt(factorial(n))
z = BigInt(factorial(r))
t = BigInt(factorial(x - z))
final = BigInt(x / (t * z))
return final
end
And error is:
Please enter N: 4
Please enter R: 3
ERROR: LoadError: InexactError: BigInt(6.247682787434490584886545740022933369407761633787846742164271645199818938450171e-16)
Stacktrace:
[1] BigInt(x::BigFloat)
@ Base.MPFR ./mpfr.jl:374
[2] combinations(n::Int64, r::Int64)
@ Main ~/Julia/File.jl:249
[3] star()
@ Main ~/Julia/File.jl:257
[4] top-level scope
@ ~/Julia/File.jl:259
[5] include(fname::String)
@ Base.MainInclude ./client.jl:489
[6] run(debug_session::VSCodeDebugger.DebugAdapter.DebugSession, error_handler::VSCodeDebugger.var"#3#4"{String})
@ VSCodeDebugger.DebugAdapter ~/.vscode-oss/extensions/julialang.language-julia-1.127.2-universal/scripts/packages/DebugAdapter/src/packagedef.jl:122
[7] startdebugger()
@ VSCodeDebugger ~/.vscode-oss/extensions/julialang.language-julia-1.127.2-universal/scripts/packages/VSCodeDebugger/src/VSCodeDebugger.jl:45
[8] top-level scope
@ ~/.vscode-oss/extensions/julialang.language-julia-1.127.2-universal/scripts/debugger/run_debugger.jl:12
[9] include(mod::Module, _path::String)
@ Base ./Base.jl:495
[10] exec_options(opts::Base.JLOptions)
@ Base ./client.jl:318
[11] _start()
@ Base ./client.jl:552
in expression starting at /Julia/File.jl:259
* Terminal will be reused by tasks, press any key to close it.
Still the same error over the exact same value. It’s really worth commenting through your lines to 100% know what you’re computing
function combinations(n, r)
x = BigInt(factorial(n)) # n!
z = BigInt(factorial(r)) # r!
t = BigInt(factorial(x - z)) # (n! - r!)!
final = BigInt(x / (t * z)) # n! / ( (n! - r!)! * r! )
return final
end
t = BigInt(factorial(x - z)) does (n! - r!)!, that is nowhere in the permutations or combinations formula. See my first comment for an edit where this particular mistake is fixed.
Thank you so much.
The correct version is as follows:
function combinations(n, r)
x = BigInt(factorial(n))
z = BigInt(factorial(r))
t = BigInt(factorial(n - r))
final = BigInt(x / (t * z))
return final
end
As @DNF said, to avoid overflow you need to convert to BigIntbefore computing factorials. It’s easiest to do this once, before the subsequent calls:
function combinations(n, r)
nbig, rbig = BigInt(n), BigInt(r) # convert to BigInt to avoid overflow
x = factorial(nbig)
z = factorial(rbig)
t = factorial(nbig - rbig)
final = div(x, t * z) # use integer division, not /
return final
end
Note that this corresponds to the built-in binomial(n, r) function.
There are more efficient ways of computing it by canceling terms from the factorials in the numerator and denominator analytically, as @DNF mentioned, but you want to focus on correctness before worrying about performance.
Hi,
No, I’m not.
First of all, why do you think something like ChatGPT hasn’t existed before? Second, I don’t know what benefit a bot-based Q&A would have for a newbie like me?
Fixed precision integer datatypes generally silently overflow (or underflow). It doesn’t mean you run out of memory (that’ll be an OutofMemoryError or some sort of crash) and it isn’t the kind of overflow where you write to the wrong memory addresses, it’s the value circling when the computation attempts to go outside its range. For an easy example, imagine a 2-bit signed integer. Its values are only -2, -1, 0 and 1. There cannot be a value of 2, so if you attempt 1+1, you circle back to -2.
Respectfully, I haven’t seen OP repeat code in this thread and I double checked just now. They were editing variable names as I suggested, albeit in a few attempts that didn’t fix the formula error.
While formulaic responses are characteristic of generative AI, they are ALSO characteristic of people who have less experience in English. Similarly, GPT detectors were observed to misidentify non-native speakers at a higher rate, paradoxically reducing the detection rate after the submitted essays’ vocabulary was edited by ChatGPT. I think we should be more cautious before making inflammatory accusations, be more open to other explanations.
It is an integer overflow. The largest Int64 is typemax(Int64) (gives 9223372036854775807). When you exceed this value then it “wraps around” to the negatives:
Since factorial grows very fast this happens very easily. In fact for Int64 the first factorial to overflow is only 21:
julia> factorial(20)
2432902008176640000
julia> factorial(21)
ERROR: OverflowError: 21 is too large to look up in the table; consider using `factorial(big(21))` instead
# Stacktrace
This is why the folks in this thread (and also the helpful error message) advise you to use BigInt instead which indeed will fill up the memory instead of overflowing.
Sorry I can’t tell what problem that could possibly fix or how it’s relevant to anything in this thread. It just looks like an unfinished method for a call taking two types, and I am curious why you wrote this.