Alright mathcels, share your wisdom in converting 64 bit integer to a string as efficiently as possible, amount of digits required to store the number as a string should be precalculated ahead of time in O(1), no loops and no complicated bullshit, just one reduction step that is constant whether the number is 0 or 18325002244893529531. Also make sure that it's not slower than existing algorithms and math behind it can be easily explained to anyone who never studied math beyond highschool, show us all that math is useful in programming and it's not just academia LARP for getting free money for achieving absolutely nothing.
I make 180k a year doing SWE and have no idea how to do what you're asking
It's strictly a math problem and most people will never have to care about this unless they want to shit out numbers really fast
I can tell that this will be slower than me just using standard library, it being in assemblyshit and not real programming language doesn't help either
>assemblyshit
>not real programming language
your assemblyshit is so shit that it straight up divides by 10, even dumbest C compiler will optimize division by 10 to a multiply and a shift.
>his cpu is so old that he needs to use those pseudo techniques
sorry, i live in 2024
there's no cpu where division is faster, have a nice day moronic assemblyshitting frogposter, the fact you post frogs is why you do not understand that your code is shit and slow, slower than even academia tier baby's first while divide by 10 in C
You're wrong.
t. froogposter
what anon wanted to say probably that modern CPUs are able to those tiny optimisations themselves.
?t=7m48s
Inefficient instructions like division are usually optimized in microcode on modern cpu. Not that some moron like you would know, what cpu do you rock? A core 2 duo?
>whats a bitshift
Black person
not everyone's field of expertise
int_to_ascii:
xor rdx, rdx
mov rbx, 10
div rbx
add rdx, "0"
test rax, rax
jnz .add_digit
mov byte [rsi], dl
lea rsi, [ascii+7]
jmp print
.add_digit:
mov byte [rsi], dl
dec rsi
jmp int_to_ascii
str(num)
too slow, but that's besides the point with your worthless non-answer
>log10
that's way too slow on any computer, any non-assemblyshitters know how to approximate this so it can be done in O(1)? Probably not and I will have to do it myself because IQfy exists only for LARPing.
10 bits equal to 1024. Log 1000 might be a better option.You wanna nightshift until number is 1 or zero . At worst you will allocate two extra digits in your string.
>any non-assemblyshitters know how to approximate this so it can be done in O(1)?
even python runtime cannot do it in O(1), i doubt such a solution exists
in any case you can begin by converting from 64 bit binary int to binary-coded-decimal format like Fortran, then the remaining work will be O(log10(n)), one step for each digit/char in the BCD
the hard part would be computing change-of-base in constant time
(C)hads have already solved this by simply casting the 64 bit integer into an array of 8 chars. You're welcome btw
Okay, so since computers store numbers in binary, there MUST be a way to correlate those base 2 bits to base 10 system and there exist instructions that can count bits, leading zeroes etc.
After refreshing a bit on math, I know that log10(x) = log2(x) / log2(10). This is very interesting as number of decimal digits required to represent a number is floor(log10(x)) + 1 as per previous post.
I can calculate approximation of log2(x) by simply using something like __builtin_clz(x), because it counts leading zeroes, however for specific 64 bit case that would be 63 - __builtin_clzll(x).
But it's invalid for case where x = 0, however every number will need at least 1 digit so I can cheat with a x | 1, meaning that the function would look something like
uint64_t floor_log2(uint64_t x) {
63 - __builtin_clzll(x | 1);
}
have a nice day moronic shitposter
>have a nice day moronic shitposter
I'm not even wrong though .That's literally the fastest way to convert an integer to a byte array, which you can either handle w/ your own library (assuming they're all of length 8) or converting it into a full C string (requiring a malloc which is slow)
nobody cares about your troony tier cope of
>le int* is le char* fr fr on god
This is now my personal blogpost, homosexuals who failed middleschool math need not apply.
>nobody cares
Op cares, and my solution is quite literally the fastest, also it's
>long is char* fr fr on god
Also I'm getting a bs in math in a few weeks so I'm probably smarter than you too
I am OP, and I said I don't care, have a nice day.
Why don't you care about the fastest solution then? Did you ask your question in bad faith?
ok so post that code of yours that I can plug into my benchmark and test framework that I already setup and lets see how fast it fails 100% of tests
What tests? All you said was
>Convert a number to a string
If you're going to ask IQfy to do your homework you might as well do it in a coherent way
I accept that you're clinically moronic.
I accept that you have no theory of mind considering other people here couldn't understand you either lol
it's okay, you don't need to cope this hard about being clinically moronic and being unable to comprehend the only thing anyone would ever want to do when it comes to converting from an integer to a string
>What's hashing?
>Storing numbers in a file? Who'd wanna do that?
I genuinely hope you're just a high schooler who will grow out of this
>>What's hashing?
the only relevant hash function for an integer is identity function, I don't remember mentioning hashing
numbers in a file? Who'd wanna do that?
>talking about fast things
>brings up filesystems that are slow
I hope someone will kill you.
Okay, so you understand that reading and writing to the file system is slow (besides memory mapped file systems ig although even those are slower.) Do you understand why we would want to *minimize* disk reads and writes?
you can minimize disk reads and writes on IQfy by not posting anymore, you fricking moronic inbred Black person who can't even comprehend what converting integer to a string means to a human being and not a mindbroken troony that doesn't comprehend the difference between 10 and "10".
>Also make sure that it's not slower than existing algorithms and math behind it can be easily explained to anyone who never studied math beyond highschool, show us all that math is useful in programming and it's not just academia LARP for getting free money for achieving absolutely nothing.
Idiotic beyond belief. Congratulations, you're dumber than a frogposter.
moronic frogposter that has div in his assemblyshit that wouldn't pass a code review in HPC department larps about being less dumb than anyone, wow.
Oh bro this is super easy
$ python -c "for i in range(2**64-1): print(f'"{i}",')" > ints.txt
$ printf "#include <stdint.h>nconst char* ints[] = { $(cat ints.txt) };"
#include <stdio.h>
#include "int2str.h"
void main() {
printf("%sn", ints[18325002244893529531ull]);
printf("%sn", ints[0]);
}
Calculating the logarithm is an assembly instruction you Black person
Post the code
at least you tried and it will run better than anything else that will be posted ITT despite needlessly wasting memory.
No I won't, do your homework by yourself you insufferable homosexual
I just checked latest intel's ISA manual and can't find instruction for integer log10, care to tell me its name?
There is an instruction in the floating point x86 ISA that allows you to calculate any logarithm. I won't spoonfeed morons like you further.
>floating point
by the time integer got converted to float, my code already returned the answer, maybe I'm not the one who should be doing homework.
Damn, your algorithm works in 10 clock cycles? You rock!
yes, log10(x) approximation isn't hard and not even the main problem, I made this thread already having solved it, but IQfytards got filtered even by this
Good for you! Make the chuds seethe:-)
Why would you expect math majors to be any good at bit-twiddling?
And why do you write like an angry incel?
computers were made by math majors to begin with
i'm just saying that converting a 64-bit integer to a character string is a problem for programmers and not mathematicians.
it is a math problem when it comes to extracting digits from a number
>frogposter
>twitch zoomer emote poster
>worthless timewasting question
like pottery
>timewasting
IQfy had to increment post ID by 1 and then convert it to a string so it could show up on your monitor in a way you can comprehend it, and inefficient code that converts it costs IQfy thousands, maybe even gorillions of dollars per year and you just added one more with your worthless post, homosexual.
>thousands
>gorillions
>for converting string
try harder newhomosexual, this shit runs on a 100$ server powered by php
#include <immintrin.h>
#include <stdint.h>
#include <string.h>
void u64_to_string(uint64_t num, char buf[static 17])
{
__m128i nx = _mm_set1_epi64x(num);
__m128i ex = _mm_cvtepu8_epi16(nx);
__m128i sl = _mm_slli_epi16(ex, 4);
__m128i or = _mm_or_si128(ex, sl);
__m128i mk = _mm_set1_epi16(0x0f0f);
__m128i an = _mm_and_si128(mk, or);
__m128i lm = _mm_set1_epi8(0x09);
__m128i cm = _mm_cmpgt_epi8(an, lm);
__m128i o1 = _mm_set1_epi8(0x30);
__m128i o2 = _mm_set1_epi8(0x37);
__m128i of = _mm_blendv_epi8(o1, o2, cm);
__m128i ad = _mm_add_epi8(an, of);
uint64_t lo = _mm_extract_epi64(ad, 0);
uint64_t hi = _mm_extract_epi64(ad, 1);
lo = __builtin_bswap64(lo);
hi = __builtin_bswap64(hi);
memcpy(&buf[0], &hi, sizeof(hi));
memcpy(&buf[8], &lo, sizeof(lo));
buf[16] = ' ';
}
>char buf[static 17]
elaborate on 3 missing characters
we must be inclusive to all use cases, and that includes stack overflow attacks (its their culture!)
>magic numbers
>magic functions
cniles are insufferable
and
>doesn't do what is expected
literally absolutely nobody understands hexadecimal nor cares to, it is self evident that string representation should be in base 10
your worthless simd code amounts to nothing
>literally absolutely nobody understands hexadecimal nor cares to
wrong, filtered, cope
all me btw
moron
say this to people who have a job, aka everyone who uses numbers like a human being and not like an incel loser
anyone who deals with bytes, bits and binary data will use hexadecimal, especially for things like mask
you'd know that if you knew C
normal people who have a job deal with things like millions of dollars in their bank account, not bytes, they want to see their clean 6 digit base 10 number, not some hexadecimal inane shit you stupid poor Black person
filtered
>zero padded hex
pathetic
It's trivial to remove the zero padding
quit bumping this useless thread and do your fricking homework already
Baffling amount of anger in OP's replies. I don't get why some anons act like this.
I think it's just a bunch of LLM prompted to try to be as enraging and time-wasting as possible
do your own homework rajesh
>no loops
why?
>just one reduction step that is constant whether the number is 0 or 18325002244893529531
why?
what does one reduction step means?
Reduction in mathematics simply means simplification, because geniuses love simplicity while low IQ's are impressed by complexity.
>Reduction in mathematics simply means simplification
but can one "reduction" use an arbitrary number of instructions?
it can, but anything that's slower than what I already have is worthless
what do you have
nothing, he's a pajeet
do your own homework pajeet
code that actually works unlike everything posted ITT so far
>code that actually works
it can't convert to a dynamic length decimal
tell me more about it
it's broken
fix it then, are you some moronic larper nocoder who can't?
I'm not doing your homework son
this isn't homework, this is an unsolved problem that you have no chance of solving since you're just a larping IQfytoddler
it does look like homework
at least give it a try
homework problems don't specify performance requirements
>I got filtered by homework tier problem
isn't a very good cope either, you should find better bait
is it or is it not your homework?
I will concede that it's a homework problem if you post it in your next reply, but only because I am betting on the fact that you are the 99.9999999999999999999999% of IQfytards and not the autist who can program and basically you will be unable to solve it anyway.
>I will concede that it's a homework problem
good
do it yourself
>no code posted
so now that it is acknowledged that you cannot solve it due to it not being a homework problem, it's time to stop posting, stick to solving your homework tier problems lil Timmy, maybe one day you will learn that in real world, numbers are formatted into strings in a lot of places and unlike your fizzbuzz, the problem presented in OP is actually useful in real world.
come on
you can do it
and I will, I was already halfway before making thi thread, however I'm not going to post code here after the fact
good boy
and this
is simplicity?
no, this is worthless algorithm for worthless base16 representation of an integer in textual form, I already adressed the fact that only base10 is relevant
#include <stdio.h>
#include <stdint.h>
int main() {
uint64_t num = 18325002244893529531;
int digits = num > 0 ? 1 + (int)log10((double)num) : 1;
char str[digits + 1];
sprintf(str, "%llu", num); // Convert integer to string
printf("Number of digits: %dn", digits);
printf("String representation: %sn", str);
return 0;
}
Oo oo, mr sam altman coming for yer jobs
Gpt end of programmers!!!
>log10
unbearably slow
>VLA
>sprintf
have a nice day
return number.ToString();
The only way I know is dividing and taking the modulo. Is there another way?
no there is not
https://jk-jeon.github.io/posts/2022/02/jeaiii-algorithm/
Ignore IQfytards ITT, watch them squirm and produce nothing of value, once this thread gets archived there will be eternal proof of IQfytards being worthless homosexuals incapable of solving anything harder than fizzbuzz type problems.
his naive solution is actually faster than his optimized lmao
>show us all that math is useful in programming and it's not just academia LARP for getting free money for achieving absolutely nothing
Kid named graphs:
Kid named machine learning:
Kid named NASA computers:
Kid named simulations:
Do you want me to go on?
I asked for useful things and everything you listed is an useless drain on money and power (electricity kind)
I'd love to see you be "useful" online without math
How do you think the device you're using to decrease the collective IQ of this platform works? Through prayer and make-belief?
The entire fricking world runs on math and every piece of software can be described by math.
But of course the entire world must change to accomodate your subjective opinion and everyone is obligated to tell you how much of a fricking moron you are. Go back to school, anon, that D you got in math isn't the end of the world
>moronic frogposter can't read graphs
I am honestly unimpressed by such in 2024
This thread is enough that you math larpers are incapable of anything useful.
>This thread is enough that you math larpers are incapable of anything useful.
Speaking of useful, perhaps you should learn about statistics and hypothesis testing? Just because you talked to 3 idiots doesn't mean the entire world/board consists of only idiots. Most people will simply ignore this thread and those that don't will just leave after you point out some dumbfrick "flaw" in their logic that isn't actually a valid counterargument
If you just want to disagree with people, go to twitter, see where being negative 24/7 gets you
Now if you'll excuse me, I'm gonna go back to learning about applied mathematics
>"you're leaving because you can't actually provide anything usef-"
Yes anon you're very smart, now why don't you get up from the toilet and go back to the kitchen, the fast food won't prepare itself
sorry not going to learn about any of this irrelevant shit, in fact I didn't even read your post as it is off-topic and I'm purely interested in what I wrote in OP
in haskell this is just
f :: Int -> String
f n = g (mod n 10, div n 10) []
where g (r, 0) acc = toEnum (r + 48) : acc
g (r, q) acc = g (mod q 10, div q 10) (toEnum (r + 48) : acc)
Hello OP
You good bait make thread
5 rubles add to you account
Parasites like (you) deserve the rope. The world would be a better place without leeches. You bring nothing of value to society. You will die being remembered as a burden. Nobody will want to truly help you in times of need.
>just one reduction step that is constant
What is a reduction step?
And nothing is constant. Everything is impermanent and subject to change, death and decay.
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
char* int64_to_string(uint64_t num) {
// Allocate memory for the string
char* str = (char*)malloc(21 * sizeof(char)); // 20 digits + 1 null terminator
// Check if allocation succeeded
if (str == NULL) {
fprintf(stderr, "Memory allocation failedn");
exit(1);
}
// Pointer for writing digits from right to left
char* ptr = str + 20; // Point to the end of the string
// Null-terminate the string
*ptr = ' ';
// Convert the number to string
do {
*(--ptr) = '0' + (num % 10); // Extract the last digit and convert it to char
num /= 10; // Remove the last digit
} while (num != 0);
return ptr; // Return pointer to the beginning of the string
}
int main() {
uint64_t num = 18325002244893529531;
char* str = int64_to_string(num);
printf("Number: %sn", str);
free(str); // Free allocated memory
return 0;
}
This implementation should be efficient and straightforward. We preallocate memory for the string, and the conversion process has a constant time complexity since we always divide the number by 10 to extract digits. The algorithm is easy to understand even for someone with basic math knowledge.
Literally took me 20 seconds with AI
How does that make you feel?
>kills program if allocation fails
>needs to allocate
>doesn't know how many digits are needed precisely
yeah this is the thing that will replace us humans, lol
log10 is enough, here's working code that you will not be able to beat even if you aren't a IQfytard
#include <cstdint>
#include <iostream>
#include <limits>
unsigned int
base10_digits(std::uint64_t const x)
{
static constexpr std::uint64_t pow10[19] = {
10ull, 100ull, 1000ull, 10000ull, 100000ull, 1000000ull, 10000000ull,
100000000ull, 1000000000ull, 10000000000ull, 100000000000ull,
1000000000000ull, 10000000000000ull, 100000000000000ull,
1000000000000000ull, 10000000000000000ull, 100000000000000000ull,
1000000000000000000ull, 10000000000000000000ull
};
std::size_t const floor_log2_x = 63 - __builtin_clzll(x | 1);
std::size_t const i = (floor_log2_x * 77) / 256; // multiply by 1 / log2(10)
return i + (x >= pow10[i]) + 1;
}
int
main()
{
std::uint64_t x = 1;
std::uint64_t prev;
do
{
std::cout << "base10_digits(" << x << " - 1) = " << base10_digits(x - 1) << 'n'
<< "base10_digits(" << x << ") = " << base10_digits(x) << 'n'
<< "base10_digits(" << x << " + 1) = " << base10_digits(x + 1) << 'n';
prev = x;
x *= 10;
}
while (x >= prev);
static constexpr auto max = std::numeric_limits<std::uint64_t>::max();
std::cout << "base10_digits(" << max << ") = " << base10_digits(max) << 'n';
}
program if allocation fails
to allocate
't know how many digits are needed precisely
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <gmp.h>
void print_large_ints(uint8_t *bytes, size_t num_bytes) {
mpz_t integer;
mpz_init(integer);
size_t i;
for (i = 0; i < num_bytes; ++i) {
mpz_mul_ui(integer, integer, 256);
mpz_add_ui(integer, integer, bytes[i]);
}
gmp_printf("%Zdn", integer);
mpz_clear(integer);
}
int main() {
// Read bytes from stdin until EOF
uint8_t *bytes = NULL;
size_t capacity = 0;
size_t size = 0;
int byte;
while ((byte = getchar()) != EOF) {
// Resize buffer if necessary
if (size >= capacity) {
capacity += 10; // Increment buffer capacity by 10 bytes
bytes = realloc(bytes, capacity);
if (bytes == NULL) {
fprintf(stderr, "Memory allocation failedn");
return 1;
}
}
// Store byte in buffer
bytes[size++] = (uint8_t)byte;
}
// Print out the large integers
print_large_ints(bytes, size);
// Free allocated memory
free(bytes);
return 0;
}
ur point being?
have a nice day moronic Black person, you're too braindead to even format your shitty garbage, didn't read
Why? AI has no problem segmenting it
If you can't read as good as AI
you will be replaced
void to_string_avx512ifma(uint64_t n, char *out) {
uint64_t n_15_08 = n / 100000000;
uint64_t n_07_00 = n % 100000000;
__m512i bcstq_h = _mm512_set1_epi64(n_15_08);
__m512i bcstq_l = _mm512_set1_epi64(n_07_00);
__m512i zmmzero = _mm512_castsi128_si512(_mm_cvtsi64_si128(0x1A1A400));
__m512i zmmTen = _mm512_set1_epi64(10);
__m512i asciiZero = _mm512_set1_epi64('0');
__m512i ifma_const = _mm512_setr_epi64(0x00000000002af31dc, 0x0000000001ad7f29b,
0x0000000010c6f7a0c, 0x00000000a7c5ac472, 0x000000068db8bac72, 0x0000004189374bc6b,
0x0000028f5c28f5c29, 0x0000199999999999a);
__m512i permb_const = _mm512_castsi128_si512(_mm_set_epi8(0x78, 0x70, 0x68, 0x60, 0x58,
0x50, 0x48, 0x40, 0x38, 0x30, 0x28, 0x20, 0x18, 0x10, 0x08, 0x00));
__m512i lowbits_h = _mm512_madd52lo_epu64(zmmzero, bcstq_h, ifma_const);
__m512i lowbits_l = _mm512_madd52lo_epu64(zmmzero, bcstq_l, ifma_const);
__m512i highbits_h = _mm512_madd52hi_epu64(asciiZero, zmmTen, lowbits_h);
__m512i highbits_l = _mm512_madd52hi_epu64(asciiZero, zmmTen, lowbits_l);
__m512i perm = _mm512_permutex2var_epi8(highbits_h, permb_const, highbits_l);
__m128i digits_15_0 = _mm512_castsi512_si128(perm);
_mm_storeu_si128((__m128i *)out, digits_15_0);
}
why obfuscate?
not my code, not obfuscation. just bit magic.
get someone else to do your university assignment/job assessment, Pedro.
Homework thread stays up for 10 hours, how?
Summergays are the worst.
I'd just use branch less and bitwise this is trivial.
>as efficiently as possible
Oh, just reinterpret the bytes of the 64 bit integer directly as characters. Supremely fast.
>But it doesn't do what I expected.
You DIDN'T SAY what you expected the output to be, so I assumed you'd be happy with this.
unsigned long number = 0x00646c776f6c6568;
char *str= (char *)&number;
Both memory efficient and O(1).
fpbp
homework thread still up what the frick jannies
>that is constant whether the number is 0 or 18325002244893529531
You want an algorithm that performs this in constant time? How would that be possible? You'll always have to perform operations based on the length of your number; so it'll always be tightly bounded by that. A computer can't perform magic.
I don't know the algorithms for integer to character conversion off the top of my head, but I presume the best you could do is θ(n).
have a nice day holy shit
This is the fastest you can go without intrinsics for atou64 with known length.
I'm not gonna bother with figuring out the other direction though, you're the one that needs it.
i just had a look at how glibc implements itoa, and its several hundred lines of C code (stdio-common/_itoa.c)
>Create a LUT with 2^64 entries for every number
>string = LUT[number]
>amount of digits required to store the number as a string should be precalculated ahead of time in O(1), no loops and no complicated bullshit, just one reduction step that is constant whether the number is 0 or 18325002244893529531
So... what you want is an integer log10 function. Rust actually has this built in natively to the standard library. What does that look like after optimizations? Well... it doesn't have loops, but it's not entirely a small number of instructions. Pic related is what gets generated.
Phone posting from a ship rn
>Length
log10(x) = log2(x) / log2(10)
Precompute = 1/log2(10) = ~0.30102999566
length = (int)ceil(fyl2x(invl2b, x))
Should be 4 instructions
i2f
fyl2x
round
f2i
I'm not gonna look up the exact names.
>Getting the digits
I can't think of a better algorithm than the standard looping division rn, maybe later.
>I can't think of a better algorithm than the standard looping division rn, maybe later.
Here's a (probably moronic) suggestion.
Use 4 bits to represent a base 10 digit.
Then 20 digits should be enough to represent any 64 bit int. Store your numbers as "digit arrays". Pre-compute the powers of 2 as said digit arrays. Implement "digit addition" in for base 10. With base-10 addition implemented, compute the individual digits of the result "naively", by a single base-10 addition of the digits of the components (plus the carry of the previous digit)
I would implemented it, but I don't know enough meta-programming and low-level optimization to do it properly, as the gist of the idea is storing the powers of 2 as precomputed base-10 digit arrays and using base-10 addition on their digit components.
>He is wasting 20% of his memory for one state
Just use 8, you don't need 9.
You can use 10 bits to represent 3 digits. It's probably the best fit, space-wise. But stuff can't be easily split into 10-bit multiples.
>mfw checking fractional aproximations of log(10)/log(2)
I had a similar idea but I discarded it because it felt over engineered and I'm pretty sure just dividing would be faster as well as 10x simpler.
I feel pretty confident that any string addition algorithm would be slower than a simple idiv.
void
f(uint64_t x, char *dst) {
static char buf[21];
char *p = &buf[sizeof buf-1];
do {
*--p = '0' + x%10;
x /= 10;
}
while (x > 0);
strcpy(dst, p);
}