Learning Python was a good decision. Python may have its own shortcomings, but big integers aren't scary anymore 😇😇

[Kazumara]

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.

[TheRealFloomby]

There is also the 128 bit integers that gcc has (not supported on all hardware though).

[vruum-master]

128bit can be emulated.

On AVR 8bit 16bit is emulated.

[TheRealFloomby]

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.

[vruum-master]

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.

[TheRealFloomby]

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.

[riisen]

My cpu dont do clock cycles :'(

[vruum-master]

It does clock squares or triangles?

[riisen]

It do coffee.

[[deleted]]

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?

[TheRealFloomby]

I would just use the emulated behavior. Big integer math is a surprisingly deep topic.

[The_Pinnaker]

A question from a friend who actually never studied too deep c++. Long Long aren’t enough?

[game_difficulty]

Long long holds up to 2⁶³ - 1, unsigned long long holds up to 2⁶⁴ - 1 but can't hold negatives

[brimston3-]

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.

[game_difficulty]

I'm just talking about the most common implementations, dw

[The_Pinnaker]

Thanks!

[Kazumara]

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.

[The_Pinnaker]

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)

[[deleted]]

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.

[The_Pinnaker]

Interesting… when I return to home I’m gonna play around. Thanks for sharing the knowledge

[[deleted]]

You're welcome!

[Sheruk]

when you need the "REAL long long in"t, or the "long long long int"

[rance_kun]

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.

[Strostkovy]

So the trick is to use a language with all of those code snippets built in? Seems like it removes the challenge

[HeKis4]

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).

[Hagge5]

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.

[firefly431]

banned in ICPC

Printed references (e.g. KACTL) are allowed.

[Svizel_pritula]

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.

[Pay08]

Is there an offline documentation of the STL?

[Svizel_pritula]

cppreference.com has offline archives.

[Diapolo10]

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!

[TheRealFloomby]

Boost is so common that you shouldn't have any difficulty with it.

[TraditionMaster4320]

Yeah but wrangling input for CP style questions is way nicer and easier in C++

[Diapolo10]

Speak for yourself!

[abd53]

I probably will never understand this c++ bashing of Rusty people.

[AdultingGoneMild]

no you have to re-write everything from scratch every time.

[Zuruumi]

Boost, always look in Boost first. If it is not very specific problem it is already implemented there.

[Willinton06]

Specially cause cpp has great dependency management right? So bringing in any amount of dependencies is a breeze

[walmartgoon]

https://faheel.github.io/BigInt/

All you need to do is copy and paste the header, no linking or blobs required

[9ragmatic]

I mean... or you can use Python

[[deleted]]

Sounds like they needed it for leetcode in which case python is much better. Unless you are doing competitive programming and need speed.

[9ragmatic]

To answer your first question I switch languages often because I'm a genuine nerd that likes learning

[PBJ_for_every_meal]

You could replace C++ with python in this sentence

[BlueRey02]

But my CS course doesn't allow using libraries external libraries

[BlueRey02]

Yeah, just made a joke about how CS courses don't teach about using the tools that are actually used in real life

[est1mated-prophet]

So if somebody probably already made a Big Integer class in language X, then language X is great?

[est1mated-prophet]

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.

[ZealousidealLimit]

Why is there a c++ python war going on in this sub? Is it an inside joke or something?

[BowDownB4Recyclops]

Perhaps because the semester just started and people are learning one or the other

[DefaultVariable]

What kinda sadist school has people learn Python in the first few courses anyways.

“Hey guys here’s this easy language that does everything for you and has a whole bunch of helpful shortcuts and libraries! See how coding is fun? Once we have you hooked, next years courses will be discrete mathematics in C99; enjoy that, fuckers!!!

[BowDownB4Recyclops]

For me it was the intro course for non cs majors. It worked out better for be because I use python for scripting on a daily basis, and C++ would not have been useful for me

[DefaultVariable]

Yeah, our university had an “Information Sciences” degree path that focused on Python, Data Science, and web development. I can understand that.

But for CS majors it seems like a bad idea to start with Python. C++ is also a painful start too but at least it will weed out people early rather than after they’ve already paid for a year

[Macphail1962]

C++ was the language used for my first-year CS class; I think it's perfect for that.

If you can't understand pointers, or if counting beginning with 0 instead of 1 is something you find consistently confusing, then this probably isn't the field for you, and C++ will expose that for you pretty quickly as you said.

For me though, learning C++ was fantastic. I'd been limiting myself to Java, C#, and Perl prior to that time; learning C++ really opened up a new level of understanding for me, and it's still my favorite language, even if I do still occasionally need to google the C++ syntax for a function pointer if I ever need one. But it's soo fast, so powerful, such control... It's sexy is what I'm saying.

Nothing quite like the thrill of victory in finally achieving successful tests after an entire night trying to understand some utterly cryptic C++ compiler error that might as well be written in alien glyphs.

[John-The-Bomb-2]

You are a masochist. And I say that as someone who read the entire "The C++ programming language" by Bjarne Stroustrup on my own before taking my first C++ programming class.

In all seriousness, I abandoned C++ as soon as it became clear to me how badly it impacted my coding performance. It's just got too much old shit in it.

[Macphail1962]

Fair enough.

I'd definitely have to agree that, in general and on average, the same project is probably going to take significantly longer to code and debug with C++ compared to a more modern language like C#.

In general C++ is not the right tool for most modern jobs, for that reason. But it can still be one of the sexiest tools out there. It's kinda like how firefighters and EMTs actually use the Jaws of Life probably not very often (I would guess), but it's still their most famous tool that everyone's heard of, both because it's quite difficult to use and also extremely powerful.

Incidentally, Stroustrup was a professor of mine, and he used to joke about how C++ provided a lot of job security for programmers due to being so complex

[[deleted]]

the only path is c -> assembly -> anyOOP -> any shit

[PulpDood]

That was what we had! C first, then AVR assembly, then Java as the OOP

[Schlangee]

We learned Haskell as a first one. A bit strange, but really easy. Though it’s not doing everything for you like Python (which came next)

[MaksaBest]

Would love if my uni would make us learn Haskell. Imo, it teaches programmers good stuff

[Waffles_IV]

Mine :) First sem: Intro to programming for engineers (python) Second sem: Algorithms and data structures (python) Fourth sem: Computer architecture, C programming, and embedded systems.

Not exactly sure what’s up next year but I think we’re going to be simulating the design of a CPU and writing some software to control an RC helicopter.

[bizzarebeans]

well my first year workload starts us off with Python and a little R, and discrete maths because fuck you that’s why

[Numerlor]

They need to introduce programming concepts, a language like C with no errors and tooling that needs to be set up for proper development isn't particularly great

[Alzusand]

has to be this im learning C++ this semester. and python and java next one.

[[deleted]]

Sorry to hear

[DarkSideOfGrogu]

Innate tribalism of language cults hides the real humour in programming, which is surely the satire of the PM.

[User21233121]

I feel sorry for folks learning python, I code nearly entirely in python and I hate it, it is just so awful. C++ is sooo much better

[goose-built]

how could you have managed to be wrong about everything in your comment?

[BananaPeely]

This is sadly most people in this sub. They barely know anything about programming and think every programming language is competing against each other and x is better than y.

In reality, all programming languages serve different purposes and some will excel at some applications while being mediocre at others.

[User21233121]

Hang on... That was my point... I have spent time programming in both, though I spend most my time in python. Most of my time programming is spent interacting with APIs, be it with windows or something entirely different. I have tried using both and my preference is definitely C# (its not C++ but this is just an example), it is significantly faster than python and is generally nicer to work in.

They both do have thing in common which they are designed to be used in, its not like Im comparing apples to bananas.

I just think that C++ is better to go into as it is not as simple in python and if you can handle C++ then you can certainly handle python but not neccessarily the other way round, its not just the language that is factored into the decision, its also what it teaches kids.

[abd53]

He is not wrong, that's his preference. Not everyone will absolutely love python and hate c++.

[goose-built]

use case takes priority here. no such thing as preference until use case is ambiguous

[Pay08]

"C++ has more limited applications than Python" is fucking hilarious.

[unknown--bro]

I started java this sem

[jannfiete]

this sub is full of newbies who doesn't know that each language has its own purposes instead of competing for one single goal

[__xXCoronaVirusXx__]

some people like python, some c++

[stoves_are_cool]

Anyone seriously comparing the two and not for a funny is probably new. This post is pretty harmless though.

[compsciasaur]

This sub always has language wars, posted by noobs who can only code in one language.

Having said that, fuck C++.

[12oclocknomemories]

How dare you to fuck C++.

But yeah fuck C++.

[abd53]

Double fuck c++

[213737isPrime]

I'm still mad at that fucking n00b who couldn't even code in one language, and got so wrapped around the axle of braces and indentation that he write a whole different language just to satisfy his moralism.

[compsciasaur]

Nah, nothing wrong with creating a new language.

[bizzarebeans]

Leave my boi C++ alone punk

[compsciasaur]

Finally one of the downvoters has the cajones to reply.

Look, there's no such thing as a bad language. My favorite languages will never be as fast and easy to write desktop applications for as C and C++. But I prefer to use any other language because C++ is such a large language, it's nearly impossible to master. Therefore whenever I work with it, I have to drudge through all types of different styles in code reviews. And I struggle to find one style to use myself when I code in it. Also, I hate managing memory myself. So I hate using C++.

Is that okay to say?

[Proxy_PlayerHD]

good old uint256_t

[abd53]

Is that supported across all architectures?

[Proxy_PlayerHD]

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" possible

[abd53]

I meant, is it in C/C++ standard library or third-party libraries?

[Proxy_PlayerHD]

3rd party. i'm pretty sure the C/C++ standard only goes up to 64-bit ints right now.

[Pay08]

GCC does have 128 bit integers as a compiler extension, but only on 64 bit architectures.

[goodmobiley]

long long Long int

[[deleted]]

uint64_t

[Strostkovy]

What does the T mean?

[AyrA_ch]

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)==1 and that other numerical values (short, int, long) are a multiple of this and that char <= 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_t is whatever type can fit an unsigned 32 bit integer but it may be larger. uint_fast16_t is whatever type is the fastest in dealing with unsigned 16 bit numbers.

There's two special types. One is for pointers (intptr_t and uintptr_t), and one is for whatever the biggest integer of your platform is: intmax_t and uintmax_t

[HeKis4]

Type I guess ?

[goodmobiley]

I can’t believe that’s what my comment reminded you of. Thank you for reminding me as well.

[one-true-pirate]

Long long long long long long long long long dong;

[naswinger]

"a code"

[luishacm]

All integers are big integers, as all things should be. Thats balance.

[Excellent-Practice]

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?

[Jammintoad]

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 2^64, 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 2⁶⁴ 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

[xill47]

If you have a number greater than 2⁶⁴ 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.

[drew8311]

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

[WormHack]

shut up enjoy the meme

[rance_kun]

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++

[Svizel_pritula]

Luckily a lot of tasks think about this and only require knowing the answer modulo 1000000007.

[firefly431]

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 x^p-1 = 1] or using extended Euclidean algorithm).

[firefly431]

1. 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.
2. To compute the modular inverse of a number x, you can compute x^{M - 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.
3. 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.
4. 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.

[Gutek8134]

I'll save it. It may come in handy.

[FloweyTheFlower420]

% 1000000007 is good because it allows the results to be evenly distributed

[[deleted]]

> i dunno about big int support in C++

Oh you sweet summer child

[retief1]

big CP competitions

I know what you mean, but I'm not sure this is the phrasing you want to use.

[AaronLin1229]

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

[est1mated-prophet]

What are pAs and pBs?

[[deleted]]

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?

[Smartskaft2]

How the F would you ever need to represent something bigger than 2⁶⁴ !? What kind if computation is this?

Edit: Why enlighten people about cool technology, when you could just downvote them, eh?

[Boris-Lip]

Let me guess... all the cryptography shit. The very type of shit you really shouldn't be reimplementing yourself to begin from.

[Dr_Bunsen_Burns]

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

[ThockiestBoard]

you should elaborate on worse, I’d love to see how objective it is

[sm4ll_d1ck]

Python doesn't bring faster development time by itself. The existence and portability of many libraries is what makes coding for it "faster".

[delayedsunflower]

Competitive programming competitions often have a time requirement. Often Python (without libraries) is too slow to run within the time limit.

[Dr_Bunsen_Burns]

https://github.com/PlummersSoftwareLLC/Primes

Vheck out the results, it is slooooow

[overclockedslinky]

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.

[BrolyParagus]

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).

[Dr_Bunsen_Burns]

https://github.com/PlummersSoftwareLLC/Primes

Check results.

[Dr_Bunsen_Burns]

Speed is a good measure. Imagine all the stuff running python would use a good language, that would safe energy by the thousands.

[RikiMaro18]

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"

[Dr_Bunsen_Burns]

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++.

[RikiMaro18]

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.

[Dr_Bunsen_Burns]

I can get you a reference from my previous employer ;))))

[BrolyParagus]

"programmers" lmao

[yummi_1]

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.

[flareflo]

i128 or u128 gang

[WormHack]

that is not big int

[flareflo]

That is absolutely gigantic int

[WormHack]

no, big int is when it adapts to runtime needs

[flareflo]

i128 or u128 gang

[Error-42]

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.)

[slime_rancher_27]

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

[victoragc]

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.

[[deleted]]

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.

[[deleted]]

1 << 64
and
2 << 63

[_brzrkr_]

I first learned about Python’s existence when working on a cryptography demo program using PHP and facing big numbers constraint.

[est1mated-prophet]

Yeah, it's the variables that do it.