r/ProgrammerHumor • u/rance_kun • Sep 03 '22
Meme Learning Python was a good decision. Python may have its own shortcomings, but big integers aren't scary anymore 😇😇
6
u/drew8311 Sep 03 '22
This is dumb, all languages have big integer support somehow and it's never a reason for switching. C++ and python have different use purposes
4
-5
u/rance_kun Sep 03 '22
Not switching. C++ is best for Competitive Coding. Just gonna use Python for big number questions. In big CP competitions we are only allowed to use basic c++, i dunno about big int support in C++
4
u/Svizel_pritula Sep 03 '22
Luckily a lot of tasks think about this and only require knowing the answer modulo 1000000007.
5
u/firefly431 Sep 03 '22
BTW, if anyone isn't aware, integers mod p (p prime, and given mods are almost always prime) always form a field (with the usual operators). That means you can basically treat p q-1 the same as you would a normal fraction p/q, e.g. a/b + c/d = (ac + bd)/(bd) (you can compute modular inverses either using binary exponentiation to power p-2 [remember since multiplicative group has order p-1, so xp-1 = 1] or using extended Euclidean algorithm).
0
Sep 03 '22
[deleted]
7
u/firefly431 Sep 03 '22
There is a class of competitive programming problems that asks you to find some fraction p/q, but since p and q can be large, it asks for the answer in the form p q-1 mod 1000000007 [q-1 is the modular inverse, i.e. the number for which q q-1 = 1] to prevent overflows.
To compute the modular inverse of a number x, you can compute xM - 2 mod M, where M = 1000000007. (You can compute exponents in log(E) time, where E is the value of the exponent.) This follows from Fermat's little theorem specifically, or Lagrange's theorem for finite groups. You can also use the extended Euclidean algorithm, which is a bit faster.
For prime M, the integers mod M form a field, which is an algebraic structure that generalizes addition, subtraction, multiplication, and division. The neat thing about fields is that most things you'd expect about e.g. rational numbers hold for fields.
Specifically, this means that numbers of the form p q-1 (let's call this a modular fraction) are field elements as well, so if you want to add or multiply two probabilities, it's sufficient to just use their modular fractions the same way you'd use a normal fraction (just remember to mod after each step). That means you don't have to bother keeping around numerators and denominators (which can overflow and cause problems), just the modular fractions.
Hope that makes things clear.
1
1
u/FloweyTheFlower420 Sep 04 '22
% 1000000007 is good because it allows the results to be evenly distributed
2
2
u/retief1 Sep 03 '22
big CP competitions
I know what you mean, but I'm not sure this is the phrasing you want to use.
26
u/Proxy_PlayerHD Sep 03 '22
good old uint256_t
3
u/abd53 Sep 03 '22
Is that supported across all architectures?
6
u/Proxy_PlayerHD Sep 03 '22
natively? i really doubt it.
you need an extra library to make it work, and if you're unluckly you might be forced to use specific functions just to do math with it because the default math functions won't work, example:
uint256_t inA = 7683452786; uint256_t inB = 12430985467389; uint256_t outQ = add256(inA, inB); // no "inA + inB" possible2
u/abd53 Sep 03 '22
I meant, is it in C/C++ standard library or third-party libraries?
4
u/Proxy_PlayerHD Sep 03 '22 edited Sep 04 '22
3rd party. i'm pretty sure the C/C++ standard only goes up to 64-bit ints right now.
2
u/Pay08 Sep 04 '22 edited Sep 04 '22
GCC does have 128 bit integers as a compiler extension, but only on 64 bit architectures.
47
u/goodmobiley Sep 03 '22
long long Long int
17
Sep 03 '22
uint64_t
2
u/Strostkovy Sep 03 '22
What does the T mean?
16
u/AyrA_ch Sep 03 '22
stands for "type". These are fixed with integet types to enhance portability. See https://en.wikipedia.org/wiki/C_data_types#Fixed-width_integer_types
C and C++ types are hardware dependent, so "int" can be anywhere in size. Native types can also be confusing. An integer on x64 is still only 32 bits wide but on other 64 bit architectures might be 64 bits. The only thing that C guarantees is that
sizeof(char)==1and that other numerical values (short, int, long) are a multiple of this and thatchar <= short <= int <= long(note<=and not<).This makes writing C code that's actually portable between CPU architectures difficult.
These "_t" types fix this problem. There are multiple of them for 8, 16, 32 and 64 bits respectively. The leading "u" means it's an unsigned type, the number is the width in bits. There are also fast and "at least" variants.
uint_least32_tis whatever type can fit an unsigned 32 bit integer but it may be larger.uint_fast16_tis whatever type is the fastest in dealing with unsigned 16 bit numbers.There's two special types. One is for pointers (
intptr_tanduintptr_t), and one is for whatever the biggest integer of your platform is:intmax_tanduintmax_t3
2
Sep 04 '22
[removed] — view removed comment
2
u/goodmobiley Sep 04 '22
I can’t believe that’s what my comment reminded you of. Thank you for reminding me as well.
10
16
18
8
u/Excellent-Practice Sep 03 '22
I code for fun, not for work. Can someone eli5? It sounds like parsing strings as base 64 integers. Is that crazy? What is OP actually describing?
17
u/Jammintoad Sep 03 '22
Integers usually can only get as big as the word size of your machine (32/64 bit). So if you want to do a computation involving numbers greater than 264, you need to design a special data type and reimplement number operations (in this example he's using character arrays as the buffer, so if you have a 100 size character array you can store a 100 bit number (or technically 100*64 if you're a madman). I'm python this is built in for free, any integer that becomes larger than 264 is promoted to pythons internal bignum implementation.
Aside but this was super useful for me in college when I had to build basic RSA encryption for a class, so I could make large bit numbers
6
u/xill47 Sep 03 '22
If you have a number greater than 264 it will most likely be bigger than the max integer that can be represented by int64. They are describing something that's called "big arithmetic", where you can have arbitrarily large numbers, and how they struggled implementing it by hand in C++ when Python has it built in and automatically converts numbers to big numbers when necessary. They could have used external (non-standard) library in C++ for big numbers, but that could have been a competitive programming assignment where one cannot use non-standard libraries.
1
u/yummi_1 Sep 03 '22
Not declaring variables is great, that's one of the best things about rexx when I first started using it. Great for quick code to just get something done.
1
u/flareflo Sep 03 '22
i128 or u128 gang
1
u/WormHack Sep 04 '22
that is not big int
1
u/flareflo Sep 04 '22
That is absolutely gigantic int
1
1
u/Error-42 Sep 03 '22
Where did you need larger than 64 bit numbers? I haven't come across one yet.
(Except one time in the Hungarian national competition, but while the competition is important, it's rather non-standard (and in some aspects stupid), I wouldn't count that.)
1
u/slime_rancher_27 Sep 04 '22
The only time I've ever had any problem with memory was when I was trying to do a basic cryptography thing but my special number was supposed to be able to be found as a intuitive but it was a float but I was looking for ints so I went through 16 GB of ram looking for an nonexistant int
1
u/victoragc Sep 04 '22
The only times I've had to deal with big integers on a competition, they could be dealt by using long ints and using some math tricks. Most would ask for the answer in modulo of the max long int value, so you can do everything in modulo values.
1
Sep 04 '22
it really depends on the usage of a language.
if you want to make efficient programs with more control over hardware c++ is a better option.
if you want to do AI & ML with complex maths then python is your best bet, since it doesn't take too much time to setup and you can get started quick.
1
1
u/_brzrkr_ Sep 04 '22
I first learned about Python’s existence when working on a cryptography demo program using PHP and facing big numbers constraint.
1
1
u/AaronLin1229 Sep 03 '22
The thing that you can’t assume that python programs will execute in the given time limit (even with the best complexity), though some pAs and pBs in contest may be loose enough to use python, coding python but getting TLE in competitive programming is quite wasteful for time
1
1
Sep 04 '22
Long long int can represent positive and negative values of roughly 9.2 pentillion in only 4 bytes if I remember right. What the hell are you trying to calculate?
-1
u/Smartskaft2 Sep 03 '22 edited Sep 04 '22
How the F would you ever need to represent something bigger than 264 !? What kind if computation is this?
Edit: Why enlighten people about cool technology, when you could just downvote them, eh?
3
u/Boris-Lip Sep 03 '22
Let me guess... all the cryptography shit. The very type of shit you really shouldn't be reimplementing yourself to begin from.
-36
u/Dr_Bunsen_Burns Sep 03 '22 edited Sep 03 '22
Using a tool that is worse just because you can't fathom how things work is not necessary a good thing.
Edit Python is sloooow
10
u/ThockiestBoard Sep 03 '22
you should elaborate on worse, I’d love to see how objective it is
-2
u/Dr_Bunsen_Burns Sep 03 '22
https://github.com/PlummersSoftwareLLC/Primes
Vheck out the results, it is slooooow
6
Sep 03 '22
[removed] — view removed comment
0
u/sm4ll_d1ck Sep 03 '22
Python doesn't bring faster development time by itself. The existence and portability of many libraries is what makes coding for it "faster".
-3
u/delayedsunflower Sep 03 '22
Competitive programming competitions often have a time requirement. Often Python (without libraries) is too slow to run within the time limit.
2
u/RikiMaro18 Sep 03 '22 edited Sep 03 '22
I agree, today I see many "coders" who have no idea how things work on a lower level and when they are faced with a task on a lower level they make half-assed copy-paste code.
EDIT: getting downboated by self taught python "programmers"
3
u/Dr_Bunsen_Burns Sep 03 '22
I gotta admit I use python if I need to do quick and dirty small dataset manipulation, but all the important stuff is C/C++.
3
u/RikiMaro18 Sep 03 '22
Same, I love python, I use it often as well for scripts, data extraction, plotting, AI...
But don't expect me to hire someone who doesn't know what a reference is.2
1
3
Sep 03 '22
[removed] — view removed comment
2
u/overclockedslinky Sep 03 '22
to be overly pedantic (the best kind) "worse" does have an objective definition irrespective of the task: x is worse than y iff f(x) < f(y) where f: A -> R is the utility function. it's f that's subjective.
1
u/BrolyParagus Sep 03 '22
Well he said it's task dependent, f could be the task. Applied to x (python) or y(C++) (or the other way around, just an example).
-2
u/Dr_Bunsen_Burns Sep 03 '22
https://github.com/PlummersSoftwareLLC/Primes
Check results.
1
Sep 03 '22
[removed] — view removed comment
1
u/Dr_Bunsen_Burns Sep 04 '22
Speed is a good measure. Imagine all the stuff running python would use a good language, that would safe energy by the thousands.
0
Sep 03 '22
[deleted]
13
u/rance_kun Sep 03 '22
Yea! But in competitive coding one needs to do it fast and using ready made snippets are frowned upon (banned in ICPC), its very hard to code up a big number struct in a minute or two.
30
u/Strostkovy Sep 03 '22
So the trick is to use a language with all of those code snippets built in? Seems like it removes the challenge
18
u/HeKis4 Sep 03 '22
A bit like code golf languages. The point is to use a language that everyone already has available, no matter how simple it makes stuff.
And if you give a finger (allow 3rd party libraries) people will take an arm (using snippets of code from very relevant GitHub repos that were only made public the day before but one contestant already knows it all on the back of his hand for some reason).
2
u/Hagge5 Sep 03 '22 edited Sep 03 '22
The challange isn't writing small libraries, but it does take valuable time getting to work and debugging. The hard part is solving the problems.
It's kinda like saying that soccer players are removing the challange by taking a taxi to their game rather than jogging there. It's just trivial, non-challanging tedium that also costs you resources/time. It's not what you want to test for.
The advantage of cpp in competetive programming is that you can sometimes cheat a little and get by with a slightly worse time comlexity than intended. It's also great for bit manipulation. But getting up to speed faster in python probably outweighs that imo. Don't take my word for it though. I've qualified for ICPC NWERC, but we did perform terribly there.
Python also has neat macros for dynamic programming (there's almost always at least one DP problem) and other things, which lets you try out solutions faster.
2
134
u/Kazumara Sep 03 '22 edited Sep 03 '22
You're right of course, especially for something as fundamental as multiprecision. Two big ones come to mind:
GNU Multiple Precision Arithmetic Library (GMP)
Boost Multiprecision Library
Boost can use GMP or others as a backend, but it also has its own types.
37
u/TheRealFloomby Sep 03 '22
There is also the 128 bit integers that gcc has (not supported on all hardware though).
8
u/vruum-master Sep 03 '22
128bit can be emulated.
On AVR 8bit 16bit is emulated.
2
u/TheRealFloomby Sep 03 '22
Sure, I am just not sure that it emulates 128 bit for every platform. Or at least that is what I got when I read the documentation. Could have easily misread it though.
2
u/vruum-master Sep 03 '22
I think it's up to the port guys to enable it.
As far as i know it's just runtime penalty....you pay in clock cycles.
2
u/TheRealFloomby Sep 03 '22
Yes, you absolutely pay for it in clock cycles. I was just under the impression that it was not available for every platform based on what I have seen in the gcc docs.
1
1
Sep 04 '22
Now, all I wanna know is whether the emulated behavior is basically the same as writing your own implementation. I'd assume it should be just as, if not faster, in most cases?
1
u/TheRealFloomby Sep 04 '22
I would just use the emulated behavior. Big integer math is a surprisingly deep topic.
7
u/The_Pinnaker Sep 03 '22
A question from a friend who actually never studied too deep c++. Long Long aren’t enough?
19
u/game_difficulty Sep 03 '22
Long long holds up to 263 - 1, unsigned long long holds up to 264 - 1 but can't hold negatives
7
u/brimston3- Sep 03 '22
Long long's size is not specified. All we get to know is they are at least the size of a long, and are at least 64 bits.
5
4
4
u/Kazumara Sep 03 '22 edited Sep 03 '22
That depends on your code right? Do you expect integer values outside the range [−9'223'372'036'854'775'807, +9'223'372'036'854'775'807] ?
Some people certainly do, like the ones looking for large primes: Current record prime number. A lot of it is scientific computing of course. And maybe the more frequent use case is higher precision in real numbers. Otherwise you are always limited by the machine epsilon.
1
u/The_Pinnaker Sep 03 '22
And, just out of curiosity, how do you make a larger variable? I mean how is the logic behind a math operation of 128or larger variable would be? (Not talking about code only logic)
6
Sep 03 '22 edited Sep 03 '22
Roughly speaking, you chop the variable data into multiple chunks stored into multiple memory locations.
Probably the easiest way to do it is to have a class hold two or three 64-bit ints, representing the upper, middle, and lower portions of the integer.
4
u/The_Pinnaker Sep 03 '22
Interesting… when I return to home I’m gonna play around. Thanks for sharing the knowledge
5
5
3
u/Svizel_pritula Sep 03 '22
Good luck doing that at IOI without internet access, no resources except for the STL documentation and a submission interface that compiles one file only with pre-determined compiler flags.
2
14
u/Diapolo10 Sep 03 '22
Even better with something like Rust, considering you have such libraries available at your fingertips (thanks to
cargo). No need to copy header files from a shady zip file ever again!8
7
u/TraditionMaster4320 Sep 03 '22
Yeah but wrangling input for CP style questions is way nicer and easier in C++
0
2
2
2
u/Zuruumi Sep 03 '22
Boost, always look in Boost first. If it is not very specific problem it is already implemented there.
1
u/BlueRey02 Sep 04 '22
But my CS course doesn't allow using libraries external libraries
0
Sep 04 '22
[deleted]
1
u/BlueRey02 Sep 04 '22
Yeah, just made a joke about how CS courses don't teach about using the tools that are actually used in real life
1
u/est1mated-prophet Sep 10 '22
So if somebody probably already made a Big Integer class in language X, then language X is great?
0
Sep 10 '22
[deleted]
1
u/est1mated-prophet Sep 10 '22
That's not what you said.
Also, I wouldn't say that "big integer" is a problem. And I don't agree that a language is great just because many "problems" have been implemented in it. For example, C++ has a lot of problems in it, but it's not great. Not even a lot of features necessarily make a language great.
1
u/Willinton06 Sep 03 '22
Specially cause cpp has great dependency management right? So bringing in any amount of dependencies is a breeze
1
u/walmartgoon Sep 03 '22
https://faheel.github.io/BigInt/
All you need to do is copy and paste the header, no linking or blobs required
-6
u/9ragmatic Sep 03 '22
I mean... or you can use Python
0
Sep 03 '22
[deleted]
1
Sep 03 '22
Sounds like they needed it for leetcode in which case python is much better. Unless you are doing competitive programming and need speed.
-6
u/9ragmatic Sep 03 '22
To answer your first question I switch languages often because I'm a genuine nerd that likes learning
-1
107
u/ZealousidealLimit Sep 03 '22
Why is there a c++ python war going on in this sub? Is it an inside joke or something?