|
hackbunny posted:
Next steps: handle rationals like complex numbers by making "rational" a modifier of a base type (rational int16, rational int32 etc.); add first-class arbitrary precision integers; then, put the two together
|
# ? Jul 21, 2017 10:17 |
|
|
# ? Jun 8, 2024 08:14 |
|
Endgame: complex rational bignum
|
# ? Jul 21, 2017 10:20 |
Athas posted:
Unless you use an arbitrary-magnitude type for 'n', the result size is still bounded. If n is a 32 bit unsigned value, your xs and ys are 16.16 fixed point signed values. The differences would be 16.16 unsigned values (the sign can be discarded since you're squaring them, the compiler would need special casing for this), if you square those you get 32.32 unsigned values. In a series sum of same-length addends, each addend past the first adds at most 1 carry, so a sum of 2**32 addends adds at most 2**32-1 of carry. So a 64.32 unsigned value would be sufficient for res. The square root of that should fit in 32.16. I'd argue that unless you have undecidable side-effects or genuinely unbounded loops, you can always determine an upper bound. (Regardless, you shouldn't be writing geometry code without understanding the limits of precision and magnitude involved. If you were writing the same thing in floating point, you should probably not even be doing a simple loop sum, but instead a summing tree to avoid problems of precision loss.)
|
|
# ? Jul 21, 2017 10:25 |
|
hackbunny posted:Next steps: handle rationals like complex numbers by making "rational" a modifier of a base type (rational int16, rational int32 etc.); add first-class arbitrary precision integers; then, put the two together You can do this in Haskell with the Ratio type, and say 'Ratio Integer' to get a representation based on a pair of arbitrary-precision numbers. It's nice and all, but you open yourself open to arbitrary growth in the Integers involved. It probably wouldn't be particularly hard for an attacker to force you to create increasingly large irreducible fractions. Maybe you could add some sort of threshold, and round once you hit 1KiB or some other magical size limit. Athas fucked around with this message at 10:38 on Jul 21, 2017 |
# ? Jul 21, 2017 10:36 |
Athas posted:You can do this in Haskell with the Ratio type, and say 'Ratio Integer' to get a representation based on a pair of arbitrary-precision numbers. It's nice and all, but you open yourself open to arbitrary growth in the Integers involved. It probably wouldn't be particularly hard for an attacker to force you to create increasingly large irreducible fractions. Maybe you could add some sort of threshold, and round once you hit 1KiB or some other magical size limit. There's also CReal, which builds up a whole computation as a series and then calculates it to arbitrary precision only upon displaying the result.
|
|
# ? Jul 21, 2017 19:35 |
|
Sagacity posted:There's a very nice (and extremely weaselly) article about it. It explains why it's actually *good* that this happened. quote:blockchain programming is fundamentally different from web development
|
# ? Jul 22, 2017 00:42 |
|
They're right, don't blame the individual developers involved. Blame everyone who thought any of this was a good idea.
|
# ? Jul 22, 2017 01:03 |
|
VikingofRock posted:There's also CReal, which builds up a whole computation as a series and then calculates it to arbitrary precision only upon displaying the result. Fun fact: Android's calculator is maintained by Hans Boehm, and is implemented with constructive real numbers.
|
# ? Jul 22, 2017 01:04 |
|
b0lt posted:Fun fact: Android's calculator is maintained by Hans Boehm, and is implemented with constructive real numbers. Extra fun fact: Hans-J. Boehm posted:I implemented the arithmetic evaluation engine for the default Android Calculator. It avoids cumulative errors, and provides arbitrarily scrollable, always accurate, results.
|
# ? Jul 22, 2017 01:18 |
|
Doom Mathematic posted:How come for(; { ... } works, anyway? Shouldn't that at least be for(;true;) { ... }? Or does an empty statement return true?? C's flexible loop statements are something that it gets very, very right, which is why derived languages tend to keep them.
|
# ? Jul 25, 2017 00:23 |
|
I mean, I know someone asked why, but the answer is that since C99, the second expression in a for statement is evaluated before the loop itself is executed. In this situation, the choice was made to replace an omitted second expression with a non-zero constant. Turns out that in C99, non-zero constants evaluated in a boolean context resolve to true.C99 standard posted:The statement for ( clause-1 ; expression-2 ; expression-3 ) behaves as follows: The expression expression-2 is the controlling expression that is evaluated before each execution of the loop body... Both clause-1 and expression-3 can be omitted. An omitted expression-2 is replaced by a nonzero constant. I wouldn't particularly say that the compiler makes it work (other than generating reasonable code for a "non-zero constant"), it's a part of the C99 language specification.
|
# ? Jul 25, 2017 00:55 |
|
Python code:
|
# ? Jul 25, 2017 05:59 |
|
KernelSlanders posted:
It is in Rust: code:
code:
|
# ? Jul 25, 2017 06:21 |
|
Gazpacho posted:The direct answer is that it works because the compiler makes it work. And the implicit result is true rather than false because a loop that implicitly terminates rather than implicitly repeating isn't much of a loop. So how come while() { ... }, with no condition, is a syntax error?
|
# ? Jul 25, 2017 08:56 |
Linear Zoetrope posted:It is in Rust: Rust doesn't have a one-character escape sequence for BEL?!
|
|
# ? Jul 25, 2017 09:29 |
|
Doom Mathematic posted:So how come while() { ... }, with no condition, is a syntax error? for the same reason for () { ... } is a syntax error sadly the reason is not that you forgot the space before the opening parenthesis, but it ought to have been
|
# ? Jul 25, 2017 09:33 |
|
Doom Mathematic posted:So how come while() { ... }, with no condition, is a syntax error?
|
# ? Jul 25, 2017 16:18 |
|
Gazpacho posted:There are no "empty expressions" in C. I don't understand what you mean by this, aren't there at least three empty expressions, possibly four, in for (;;) { }? Does ; by itself evaluate to true? In any case, it doesn't make sense that omitting the condition in a for loop and omitting the condition in a while loop don't do the same thing. That's strangely inconsistent language design.
|
# ? Jul 25, 2017 20:32 |
|
Doom Mathematic posted:I don't understand what you mean by this, aren't there at least three empty expressions, possibly four, in for (; { }? Does ; by itself evaluate to true? They just decided to add some special cases to the for loop syntax. That's all there is to it. You are thinking about this too much.
|
# ? Jul 25, 2017 20:47 |
|
Here's another fun C oddity.code:
This still works in C++
|
# ? Jul 25, 2017 20:52 |
|
Doom Mathematic posted:I don't understand what you mean by this, aren't there at least three empty expressions, possibly four, in for (; { }? Does ; by itself evaluate to true? In a while loop, the expression just isn't optional. Nobody ever suggested that C was a garden of pure ideology. It gets the job done. Gazpacho fucked around with this message at 04:51 on Jul 26, 2017 |
# ? Jul 25, 2017 21:40 |
|
Spatial posted:Here's another fun C oddity. I have Stockholm syndrome because this seems totally normal and expected and cool to me.
|
# ? Jul 25, 2017 22:00 |
I think I just saw my first coding horror in the wild (My own code notwithstanding.) The objective of this function was to distribute a certain number of hours over a month, such that it would fill all available hours on days that still had available hours first, and if it needed to overflow capacity it would distribute the remaining hours evenly across all days (and depending on an option, this could include days that do not allow hours.) Hours have to be divisible by a certain time step (i.e. 15 minutes, 20 minutes, 30 minutes etc.) The solution? Loop until the hours have all been distributed based on the time step (e.g. if someone wants to distribute 100.000 hours in 30 minute steps it would loop 200.000 times at least to distribute the hours) and for every iteration loop through all days in the month and deposit the hour value of the time step on that day if it has available hours. If a time step was deposited its value is subtracted from the hours to deposit. If the algorithm loops through the entire month without depositing anything, start ignoring available hours and deposit on days that allow hours. The outer loop exits only when all hours have been deposited. I asked if I could rewrite it, not so much because it's an O(hours to distribute) algorithm that should be an O(1) algorithm, but more because trying to follow it/fix bugs in it is a pain in the rear end, but got told there was no way to solve the problem in other ways (I also got told the assymptotic running time was really constant, because reasons) and no need for premature optimisations. Joda fucked around with this message at 22:26 on Jul 25, 2017 |
|
# ? Jul 25, 2017 22:18 |
|
Joda posted:I asked if I could rewrite it, not so much because it's an O(hours to distribute) algorithm that should be an O(1) algorithm, but more because trying to follow it/fix bugs in it is a pain in the rear end, but got told there was no way to solve the problem in other ways (I also got told the assymptotic running time was really constant, because reasons) and no need for premature optimisations. All algorithms have O(heat death of the universe) as an upper bound on their runtime, which as far as we know is a constant, which means all algorithms are O(1). Also, I'd love to see your O(1) solution to this problem. Sure you got your notation right there?
|
# ? Jul 25, 2017 22:33 |
TooMuchAbstraction posted:Also, I'd love to see your O(1) solution to this problem. Sure you got your notation right there? I'm probably wrong, but I think so? There's a constant number of days in a month, and I'm like 99% sure there's a solution whose running time will not depend on the number of hours to distribute. Too tired to wrack my brain with it right now, but I'm interested enough to give it a shot later.
|
|
# ? Jul 25, 2017 23:12 |
|
I think there is a closed form solution, but I'm not thinking much.
|
# ? Jul 25, 2017 23:14 |
|
Joda posted:I'm probably wrong, but I think so? There's a constant number of days in a month, and I'm like 99% sure there's a solution whose running time will not depend on the number of hours to distribute. Too tired to wrack my brain with it right now, but I'm interested enough to give it a shot later. Does your fancy O(1) solution take into account leap years?! how about months that don't have the same number of days of which there are many.
|
# ? Jul 25, 2017 23:36 |
|
ASP drove me up the wall at work earlier. I've never formally learned, so I basically dived into the deep end with it, but I was having a real hard time trying to get a SQL Server RecordSet as some kind of array I could gently caress around with in ASP. I got it eventually, but because there's no real good way to print an object in ASP for debugging, I wrote it to a JSON that was being written out to another file that I actually could read and it looked like a plain old array. As it turns out, it was actually a two-dimensional array that got flattened out when written to a JSON for some reason, which makes sense in hindsight, but it's still kind of annoying to deal with. As you'd expect, accessing any object in that array requires two coordinates, column number and row number. I have no idea why, but this array was ordered by column first, which means that getting the length of this array meant I was getting the column count, which kind of sucks because the column count is static and I wanted to iterate over an indeterminate number of rows! UBound at least has an optional parameter that lets you identify which dimension of the array you want to get a count of, which is helpful, at least. Another thing that just baffled me about ASP earlier is how it handled this for loop (written in Python for convenience): code:
|
# ? Jul 25, 2017 23:59 |
|
Joda posted:I asked if I could rewrite it, not so much because it's an O(hours to distribute) algorithm that should be an O(1) algorithm, but more because trying to follow it/fix bugs in it is a pain in the rear end, but got told there was no way to solve the problem in other ways (I also got told the assymptotic running time was really constant, because reasons) and no need for premature optimisations. Sounds like a premature optimization. What's the business problem that speeding this up will solve?
|
# ? Jul 26, 2017 00:59 |
|
code:
|
# ? Jul 26, 2017 03:04 |
|
Joda posted:I'm probably wrong, but I think so? There's a constant number of days in a month, and I'm like 99% sure there's a solution whose running time will not depend on the number of hours to distribute. Too tired to wrack my brain with it right now, but I'm interested enough to give it a shot later.
|
# ? Jul 26, 2017 03:34 |
|
Spatial posted:Here's another fun C oddity. z and w are things working totally normally. y is undefined behavior that will probably work on modern architectures. Thou shalt not form any pointers that ever point to anything besides 0 or between the start of an array and one past its end, even if you never dereference them. It'd crash on some old CPUs with dedicated base and offset registers (like things with a 16 bit memory space and 8 bit registers where pointers are done with register pairs).
|
# ? Jul 26, 2017 05:25 |
|
Foxfire_ posted:z and w are things working totally normally. y is undefined behavior that will probably work on modern architectures. y is always legal because a[x] is defined as *(a + x).
|
# ? Jul 26, 2017 05:37 |
|
Foxfire_ posted:z and w are things working totally normally. y is undefined behavior that will probably work on modern architectures. Incorrect. C99 language spec: quote:6.5.2 Postfix operators The expression 7[x] is not only valid, it's guaranteed to have the same result as x[7], because the conversion rules for binary + are transitive. Foxfire_ posted:Thou shalt not form any pointers that ever point to anything besides 0 or between the start of an array and one past its end, even if you never dereference them. Wat. I don't know how you ever came to that conclusion. A pointer is just an address number; if you don't dereference it, it does nothing. C and C++ are not garbage-collected languages, a pointer pointing to something it doesn't own / cannot own is harmless as long as you do nothing with it. Foxfire_ posted:It'd crash on some old CPUs with dedicated base and offset registers (like things with a 16 bit memory space and 8 bit registers where pointers are done with register pairs). Are you thinking about the old 8088 and its segment selector registers? It wouldn't quite crash, no, although it might not do what you were planning. Working with segment registers is basically identical to working with paged RAM, just much simpler and easier. The worst part of it was just having to deal with separate types for near/far pointers. ullerrm fucked around with this message at 06:26 on Jul 26, 2017 |
# ? Jul 26, 2017 05:56 |
|
It's defined in C89 and C++, undefined in C99 (type constraints). It's also pretty benign.
|
# ? Jul 26, 2017 05:59 |
ullerrm posted:Note that, IIRC, this changed in C++11 and later. Do you have any details on this? I can't find anything about this change online.
|
|
# ? Jul 26, 2017 06:02 |
|
if you would ever write something like 7[x] you are such an irredeemable idiot that no standard can possibly help you
|
# ? Jul 26, 2017 06:06 |
|
VikingofRock posted:Do you have any details on this? I can't find anything about this change online. I stand corrected, it still allows either ordering as of C++14.
|
# ? Jul 26, 2017 06:26 |
|
ullerrm posted:Wat. I don't know how you ever came to that conclusion. A pointer is just an address number; if you don't dereference it, it does nothing. C and C++ are not garbage-collected languages, a pointer pointing to something it doesn't own / cannot own is harmless as long as you do nothing with it. Doing pointer arithmetic that creates a bad pointer puts you straight into undefined behavior territory (though it's one of those undefined behaviours which is often tolerated by compilers). See 5.7.4 in the standard. For example, merely computing the value can cause an overflow trap if it's outside the allowed range (while if the newly-computed pointer is inside the allowed range, the compiler must ensure that it doesn't overflow).
|
# ? Jul 26, 2017 07:47 |
|
|
# ? Jun 8, 2024 08:14 |
|
ullerrm posted:Wat. I don't know how you ever came to that conclusion. A pointer is just an address number; if you don't dereference it, it does nothing. C and C++ are not garbage-collected languages, a pointer pointing to something it doesn't own / cannot own is harmless as long as you do nothing with it. Wrong on that count. 7[x] is fine because the 7 isn't a pointer. If you make a pointer to address 7, it's undefined behavior whether you use it or not. Jabor posted:Doing pointer arithmetic that creates a bad pointer puts you straight into undefined behavior territory (though it's one of those undefined behaviours which is often tolerated by compilers). See 5.7.4 in the standard. Often tolerated, with the notable exception of making certain null checks invalid if you create a pointer to a field before checking against null. Edit: at least I think that variant of the problem existed. I know 'harmless' dereferences can render null checks invalid. Dylan16807 fucked around with this message at 08:12 on Jul 26, 2017 |
# ? Jul 26, 2017 08:03 |