Neat algorithms

[brucehoult]

Note that many software implementations of trees in general, when manipulated in RAM, are a lot less efficient than expected from the algorithms due to accesses all over the place that lead to many cache misses. So in that respect, the choice of algorithm and data structures are key. It's not just a problem with RAM either, any medium that can be accessed more efficiently as consecutive blocks (hard drives being also that way for instance) are concerned.

If you're doing really random pointer chasing, such that each access is just as likely to hit a new memory page as well as a new cache line then you're likely to lose more performance to TLB refills than to cache misses.

Look at the very popular ARM A53, as used as the LITTLE processor in most current phones and tablets, and the main processor in RaspberryPi or lower end phones.  It has typically 16 KB or 32 KB or 64 KB of L1 cache (256, 512, or 1024 cache lines), but it has only *10* L1 TLB entries, and a secondary L2 TLB with 512 entries.

I don't know how much time it takes for a L1 TLB miss that hits in L2, but as soon as you have more than 40 KB of data that you are jumping around in randomly you're going to start getting frequent TLB misses as well as the cache misses.

[Nominal Animal]

For in-memory data structures, I like hash tables with chained entries, the hash key stored in the entry, and the table itself an array of pointers:

Code: [Select]

struct hash_entry {
    struct hash_entry *next;
    size_t  hash;
    /* Data */
};

struct hash_table {
    size_t  size;  /* Number of entries in entry pointer array */
    size_t  used;  /* Number of entries in the table */
    struct hash_entry **entry;
    /* pthread_rwlock_t  rwlock; for thread-safe operation */
};
This is definitely not the most efficient way to go about it.  Pointer chaining trades some efficiency for robustness: if you have an entry, insert never fails.  Including the hash value itself in each node trades memory for ease of use, and reduces the number of full comparisons needed when a pointer chain grows long.

Essentially, it trades some efficiency, to keep itself simple and robust, and to avoid any pathological cases (like "you must resize the hash table now or you cannot insert that entry").  Even the thread-safe locking scheme is obvious: a single rw-lock protects the hash table structure.

I would not call this neat, though; it's just simple and robust.

[westfw]

many software implementations of trees in general, when manipulated in RAM, are a lot less efficient than expected from the algorithms due to accesses all over the place that lead to many cache misses.

In theory, that doesn't matter, because you're only affecting K in the overall t = K * f(N) performance equation.  If your N really justifies going from a log(N) algorithm to log(log(N)) (Tango Trees, say. No, wait - that's the "competitive ratio", a term I don't understand), then cache misses are going to need to be REALLY REALLY EXPENSIVE before the improvement goes away. I mean, for 2⁶⁴ items, log₂(n) is 64 and log₂(log₂(n)) is ... 6.  But going from the O(N) to O(log(N)) is going to pretty clearly be a huge win, even with ~64 "cache misses", compared to 2⁶⁴ "perfect" memory accesses.
In reality, of course:

• K CAN be really large.
• You can build a career, or a business, out of improving K.
• It's pretty common for someone to use an algorithm on a data set size where it doesn't really make sense.  Because it's built into the language, or "part of the standard", or "company policy."  (I once ported a Fortran SORT subroutine that was implemented by running a system sort utility (separate program!), after setting up a shared memory area...  I'm pretty sure (now!) that it would have been a better idea to just replace it with a more modern library function...)

[Nominal Animal]

If comparing the real-world difference between say O(log N) and O(N) algorithms is interesting, implement a radix sort (which is O(N) but with a rather high constant factor, and requires rather large amount of extra memory), and compare it to other sort algorithms.  To make it a bit more realistic, use key-value pairs as elements to be sorted, say double and a pointer on 64-bit architectures.

For very small N, insertion sort is the best choice in practice, even though it has O(N²) time complexity.  Most common sorting algorithm is probably quicksort, even though it has O(N²) rare worst-case and O(N log N) expected time complexity.  In practice, radix sort (having O(N) time complexity), temporarily converting the IEEE-754 double keys so that all finite values sort according to their unsigned integer value by flipping either the sign bit or all other bits, will be fastest for large enough N.  However, the exact point depends heavily on the radix size used (determining the size of the temporary arrays needed), and how well that matches the hardware architecture used; and even then, because it is cache-intensive, it can negatively impact surrounding code as it evicts a lot of data from the caches.  The last time I checked this thoroughly, the changeover was N roughly a couple of million, but this was a decade ago on x86-64.


Brucehoults post and example code that sorts input lines by reading the data into a (scapegoat) tree, is also an excellent example of how the chosen algorithmic approach affects real-world performance.

In mid-nineties, a C course I took required one to implement a simplified 'sort' command in an Unix environment (Solaris, if I recall correctly). I used a very similar approach, reading lines into a binary search tree, implementing the entire program in about 300 lines, a third of which were comments.

This was the era of spinning disk hard drives, and I/O speeds were much slower than they are today with SSD drives and multi-gigabyte RAM sizes (making many workloads completely cacheable in RAM).  Reading the input was the clear bottleneck.  If you first read the input to memory, then sort them, then you wait for all I/O to complete before you start computation (sorting).  If you read the lines into a sorting data structure like a tree, you essentially do the computation while I/O is still underway; and your sort is basically complete, when I/O completes.  This means that the read-then-sort takes much longer, using real-world wall-clock measurement, than reading the lines into a tree; even if the read-to-tree uses somewhat more CPU time.

(Today, if the input is in a file, it is likely cached, and the I/O is essentially free.  You need to use a slow pipe (a network connection or similar), or a slow(ish) generator, to see the difference.)

Just like comparing algorithms based on their big-O notation, even terms like fast must be carefully qualified, to convey real-world applicable information.  When we say "fast", we can refer to CPU time, or wall clock time (or, if we are stupid, our gut feeling about the algorithm).
For us humans, interactive tasks' speed should be measured in real-world wall clock time, but batch and background jobs in CPU time.  Similarly, asymptotic time behaviour is only really indicative of the big-N behaviour, and does not tell us anything about the constant factors.

Even comparing algorithm behaviour via real-world testing must be categorized into at least two sets: microbenchmarks that ignore everything except the task at hand, in an effort to compare apples to apples; and true benchmarks, where tasks similar to or simulating real-world computing tasks are compared to each other.

This means that to be able to sort in a neat way, one should have several different sorting algorithms and approaches in their toolbox ready to be used.  The neat part, then, is picking the correct ones to match the use cases and user preferences for the kind of tasks.

[T3sl4co1l]

A valuable lesson about modern CPUs is, computation is almost for free.

And by "modern", I mean anything with generous caches, say Pentium 1 or 2 level and up.  Since after all, that's why caches exist!

Don't be afraid to waste computation, as long as it contributes to a faster overall result; given other constraints of course (like total CPU usage or battery consumption).  Concentrate more on IO latency and cache hits, than on inner loops.  (If in doubt, profile!)  Now that SMP is pervasive, don't be afraid to parallelize operations.  Example from simulation, you might test a bunch of timesteps at once (dispatch a different matrix initialization and inversion operation to each core), you only need one to work but you can test a bunch in parallel rather than having to wait for all the failures first.

Tim

[coppice]

A valuable lesson about modern CPUs is, computation is almost for free.

Unless the computation is mobile, where every unnecessary instruction drains the battery a little more.

[legacy]

This was the era of spinning disk hard drives, and I/O speeds were much slower than they are today with SSD drives and multi-gigabyte RAM sizes (making many workloads completely cacheable in RAM).  Reading the input was the clear bottleneck.  If you first read the input to memory, then sort them, then you wait for all I/O to complete before you start computation (sorting).  If you read the lines into a sorting data structure like a tree, you essentially do the computation while I/O is still underway; and your sort is basically complete, when I/O completes.  This means that the read-then-sort takes much longer, using real-world wall-clock measurement, than reading the lines into a tree; even if the read-to-tree uses somewhat more CPU time.

This is what layer0 and layer1 do on my filesystem, but they are under the constraint that ... there is still no journaling, and you have to guaranty somehow that the consistency of the filesystem is not entirely compromised when the CPU crashes or when the board loses the power supply.

This introduces a trade-off on how large you can do your DMA-window when the increasing of IO performance tells you to make it the largest possible, with even the time-window the largest possible.

In short, this is telling you to consider a harddrive like if it was a block of large shared non-volatile ram, with a built-in coherent cache handler.

We will have this in the future (I do believe first in PDAs and Tablets) as soon as the flash-storage technology will be replaced by FeRam for the same production cost (I have made a prototype, 64Megabyte FeRam SSD cost 60 euro, and it's MEGA byte, not GIGA byte).

In the meanwhile, we still have to deal with ram unable to be volatile, so it loses data on crashes, so ... you have to reduce the window during data-moving from ram to disk, even if this means that the block that you are writing a block down to the disk is going to be modified again in a couple of cycles.

The trade-off requires you a myopic vision

You need to reduced time window in your to guaranty the coherency of the b+tree algorithm when it's structure is modified, and since you cannot have a large time window, you will have a lot of cases when you will write blocks that you would have better to keep in ram because they represent "temporary files", so information that in the long time will not even go copied on the hard-drive, and they simply waste IO cycles.

[legacy]

I really like the RISC-OS/Classic (=<4.39) filesystem, you are afraid of no crash because its IO time-window is so narrow that it goes almost on every data-change.

Do you modify a byte? The block is immediately written back on the harddrive.

It's solid as a stone, but it's damn slow 

[SiliconWizard]

many software implementations of trees in general, when manipulated in RAM, are a lot less efficient than expected from the algorithms due to accesses all over the place that lead to many cache misses.

In theory, that doesn't matter, because you're only affecting K in the overall t = K * f(N) performance equation.  If your N really justifies going from a log(N) algorithm to log(log(N)) (Tango Trees, say. No, wait - that's the "competitive ratio", a term I don't understand), then cache misses are going to need to be REALLY REALLY EXPENSIVE before the improvement goes away.

Well not really. It's all in the break-even point for N for different algorithms on a given platform... (also and as I hinted above, I'm not talking just about cache misses, but anything that could make accesses more expensive if they are further apart.) This point is not trivial to find theoretically and  the corresponding N could be larger than you may initially think.

And with that said, I'm not just talking about algorithms that have a different complexity in O(N). Just picking the most efficient algorithm for a given context amongst algorithms of similar complexity is no trivial task. For instance, some sorting algorithms in O(N.log(N)) have better "locality" than others, which makes them more efficient any time locality matters in terms of access time.

With that in mind, many implementations of tree-based algorithms are definitely not very efficient due to locality issues. Good implementations of trees in that respect definitely take some serious thought.

[brucehoult]

A valuable lesson about modern CPUs is, computation is almost for free.

Unless the computation is mobile, where every unnecessary instruction drains the battery a little more.

But orders of magnitude less than an unnecessary memory load, especially from actual RAM.

[westfw]

It's all in the break-even point for N for different algorithms on a given platform.

Well, sure.  But if you're contemplating moving from an N² algorithm to an N*log(N) algorithm because N is getting "big", you probably don't need to immediately worry that you'll end up with an Nlog(N) algorithm that is sub-optimal due to cache locality issues...  (What's that saying?: "best is the enemy of better")
(By all means: MEASURE!)

[mrflibble]

A valuable lesson about modern CPUs is, computation is almost for free.

Unless the computation is mobile, where every unnecessary instruction drains the battery a little more.

But orders of magnitude less than an unnecessary memory load, especially from actual RAM.

Mobile, shmobile. Who the fuck cares about mobile, except for people wanting to make a phone call or people looking to cultivate an attention deficit disorder? Yeah yeah, phone faster than some old chippie in 1960's rocket, got it. Still too slow!

Where can I get one of those modern CPUs where computation is almost free? Or alternatively, where can I adjust this reality's dictionary lookup for "almost"? Sure computation is almost for free, but not nearly almost enough! Not only is there an endless supply of better fools to mess with any attempt at making stuff foolproof, there is also an endless supply of "better" problems to counteract the low low price of computation. Sure, my computer is significantly more capable than whatever I had 10 years ago. Yet, somehow I keep running into problems that aaaaaalmost fit ... but not quite.

Computation may be cheap and memory is cheap not super expensive, but you never have enough of either. For example, for some number theoretical mucking about I use a list of precomputed primes. Sure you could run a sieve from scratch every time you need some primes, but that does take longer, uses more energy, and did I mention it takes longer? Besides, at some point the sieve no longer fits main memory, and you will have to start using external storage. And then you find that the files are so big that you had better compress it. And then you find out that a lookup of "is this number in the list" requires a seek in the list on external storage, which results in a seek in a compressed file, which is generally not all that supported by your chosen compressor. Oh sure you can chop it up into several files, but that is just so arbitrary.

A large list of primes on which you want to do fast search operations is also a nice example of where you would like log(log(n)) instead of log(n). For ~ 2³² entries a regular binary tree takes ~ 32 operations to do a search. If you can do that in log(log(n)) operations you go from 32 to 5. A factor of 6 in runtime can be sufficient motivation to use something a little more complex. Besides, if we all valued simplicity so much, why don't I see an abacus on every desk?

If a hideous compressed tree of trees of trees is significantly faster than the happy rainbow abacus, I will happily pay the brainfuck once.

And speaking of brainfuck ... https://esolangs.org/wiki/Language_list#B

I've been meaning to play around with BrainHack, but I am too chicken. I think I spot a "Danger! Massive time sink!" sticker on it, but I don't dare take a closer look.

Oh yeah, almost forgot ... While constructing some random prime trees I noticed that to build a balanced tree from a monotonic sequence for lowest cost (no rearranging of unbalanced trees while inserting) it was easiest to do that using the in-order vs in-memory transformation that Nominal Animal mentioned waaay back.

[NorthGuy]

A large list of primes on which you want to do fast search operations is also a nice example of where you would like log(log(n)) instead of log(n). For ~ 2³² entries a regular binary tree takes ~ 32 operations to do a search. If you can do that in log(log(n)) operations you go from 32 to 5. A factor of 6 in runtime can be sufficient motivation to use something a little more complex.

If you search primes within 32-bit numbers, you have only 2G numbers to test (after eliminating even numbers which are not primes). So, you only need 2G-bit lookup table - 256MBytes of memory. Today, this is not much by any means. 4GByte lookup table will give you all primes in 40-bit numbers. And this is still quite modest amount of RAM by today's standards. One lookup and you're done. That is how you get things done when you have lots of resources, not by applying older algorithms which were designed to circumvent resource scarcity.

[SiliconWizard]

A large list of primes on which you want to do fast search operations is also a nice example of where you would like log(log(n)) instead of log(n). For ~ 2³² entries a regular binary tree takes ~ 32 operations to do a search. If you can do that in log(log(n)) operations you go from 32 to 5. A factor of 6 in runtime can be sufficient motivation to use something a little more complex.

If you search primes within 32-bit numbers, you have only 2G numbers to test (after eliminating even numbers which are not primes). So, you only need 2G-bit lookup table - 256MBytes of memory. Today, this is not much by any means. 4GByte lookup table will give you all primes in 40-bit numbers. And this is still quite modest amount of RAM by today's standards. One lookup and you're done. That is how you get things done when you have lots of resources, not by applying older algorithms which were designed to circumvent resource scarcity.

True. Of course it all depends on the application and the machine it will run on. Wasting that much memory in some cases is largely justified, in others not so much. But your point in general is worth considering.

In some cases, there are also ways to circumvent the need and translate it to something else. For instance, here, you may actually not NEED to test any integer number being prime or not. It's sometimes possible to transform your approach by generating prime numbers instead of having to test them, something that's much faster than testing for primality. You sometimes need to think outside the box.

The same idea can be applied in many cases. A trivial one, for instance, would be generating sorted lists. If your application actually gets items one by one, it's much faster to insert each at the right place than to just insert each new one at the end of the list and re-sort the entire list after each, if you need the list to be sorted at all times. It may sound obvious, but in practice you often encounter naive approaches like the latter!

[mrflibble]

A large list of primes on which you want to do fast search operations is also a nice example of where you would like log(log(n)) instead of log(n). For ~ 2³² entries a regular binary tree takes ~ 32 operations to do a search. If you can do that in log(log(n)) operations you go from 32 to 5. A factor of 6 in runtime can be sufficient motivation to use something a little more complex.

If you search primes within 32-bit numbers, you have only 2G numbers to test (after eliminating even numbers which are not primes). So, you only need 2G-bit lookup table - 256MBytes of memory. Today, this is not much by any means. 4GByte lookup table will give you all primes in 40-bit numbers. And this is still quite modest amount of RAM by today's standards. One lookup and you're done. That is how you get things done when you have lots of resources, not by applying older algorithms which were designed to circumvent resource scarcity.

Yeah, my bad. I could have typed a bit more to be more clear. With "a tree with ~ 2³² entries" I meant a tree with exactly 2³² -1 unique entries that are prime numbers. So a binary tree with N=4294967295 nodes, each node being a prime number, and each number being unique. When viewed as a sorted list, the numbers are not required to be consecutive primes, nor is the smallest number required to be 2. Whatever set is convenient for the problem at hand.

Anyways, the main point being: "4294967295 unique prime numbers", as opposed to "all prime numbers below 4294967296".

So for example a binary tree with 4294967295 nodes, the smallest entry being 2, and the largest entry being 104484802043. With 104484802043 being the 4294967295th prime. Also, log₂(104484802043) is about 36.6, so a 37-bit number.

And while we're at it ... a 4 GByte LUT as described (eliminate even numbers, keep track of the rest) unfortunately only gets you up to 36-bit numbers, not 40-bit numbers.

That said, I agree that you should use the resources available, and not use old shit that is no longer relevant. Unfortunately infinity is fucking big, even if it is countable. So even if I limit myself to boring 48-bit primes, that still takes more than a few seconds to sieve. All 32-bit numbers? Sure, about half a second or so. But half a second or so multiplied by 2¹⁶ does take longer than one cup of coffee. And 48-bit is the totally arbitrary constraint that more or less translates to "big enough that measured properties are statistically relevant". And it is also big enough that I need to be more careful in my C++ coding, because while writing to the histogram bins I manage to fuck up some memory access. Segfault, weeeey! Probably in the OpenMP section where I recombine the results of all threads.

And also, the 2³² was an arbitrary example because of nice round numbers. As in log₂(N) = 32, and log₂(log₂(N)) = 5. I could just as easily have picked 2⁶⁴ as example, the nice round numbers then being 64 and 6.

In some cases, there are also ways to circumvent the need and translate it to something else. For instance, here, you may actually not NEED to test any integer number being prime or not. It's sometimes possible to transform your approach by generating prime numbers instead of having to test them, something that's much faster than testing for primality. You sometimes need to think outside the box.

Absolutely. Transforming a problem into another form is my favorite way of solving problems. It's also the main reason (or so I tell myself ) why I try to solve toy problems and little puzzles. Not so much for the actual solution, but more as a good way to learn different ways of solving various problems. For example Project Euler has a nice collection. And after solving a particular problem you can take a look on the forum to see how other people did it. Some of it is "Yeah yeah, I did that too", or "Hah, my way is better!", but there is also plenty of "Doh! Why didn't I think of that?".

[SiliconWizard]

For example Project Euler has a nice collection. And after solving a particular problem you can take a look on the forum to see how other people did it. Some of it is "Yeah yeah, I did that too", or "Hah, my way is better!", but there is also plenty of "Doh! Why didn't I think of that?".

I just registered for some fun. Ran into some issue with the first problem though: https://projecteuler.net/problem=1
I double and triple-checked my answer, and the site still thinks it's erroneous. Could you check? Maybe I'm just tired.

[NorthGuy]

Anyways, the main point being: "4294967295 unique prime numbers", as opposed to "all prime numbers below 4294967296".

It is generally irrelevant whether the numbers are consecutive primes or any other numbers selected by any criteria. What matters is the density. If density is high enough, you can build a lookup table (which has '1' if a number is in the set or '0' otherwise), which may take more space than the tree, but will eliminate the search completely - you just look it up. But since we now have more memory than ever before we can allow yourself a luxury of consuming them and make your search really fast.

32-bit primes (or 37-bit, or even 40-bit for that matter) are a bad example because the density is high enough and lookup table takes less space than the tree. So, you should prefer the lookup table anyway. However, if the density is low, you may use the lookup table anyway, even if it takes more memory than the tree - just because you can summon enough resources. You couldn't do this before, but you can now - hence the benefit of more resources.

Unfortunately, in real world, most of computation resources are simply wasted providing nearly no benefits.

And while we're at it ... a 4 GByte LUT as described (eliminate even numbers, keep track of the rest) unfortunately only gets you up to 36-bit numbers, not 40-bit numbers.

My mistake. 40-bit primes would need 64 GByte table. Would be crazy 20 years ago. Very feasible now.

That said, I agree that you should use the resources available, and not use old shit that is no longer relevant. Unfortunately infinity is fucking big, even if it is countable.

Very true. If you try to count it, even you grand-children won't be able to finish. But most of tasks are finite. I haven't felt constrained by resources on PC for a long time. If you never hit the limit, it's as good as infinite.

[mrflibble]

I just registered for some fun. Ran into some issue with the first problem though: https://projecteuler.net/problem=1
I double and triple-checked my answer, and the site still thinks it's erroneous. Could you check? Maybe I'm just tired.

Just solved it, so seems to check out fine for me. Mainly two sanity checks:
- if you plug 10 into your code, does it give the known correct answer of 23?
- if you plug in 20, does it then return 78, or something else?
Those two are simple enough that you can check 'm by hand, and will catch the typical off-by-1 bug, and the other candidate in this case being double counting.

Anyways, seems to works fine. Maybe just add some coffee.

[SiliconWizard]

Anyways, seems to works fine. Maybe just add some coffee.

Damn. Turns out I needed some coffee. Nevermind.

[T3sl4co1l]

Hmm, this should be the solution, no?  In handy JS format, so you can pop open F12 and copy-paste it.

Code: [Select]


[SPOILERS]

.
.
.


.
.
.


.
.
.


function summultiples(below) {

function triangular(n) { return (n*n + n) / 2; };

below--;
var threes = triangular(Math.floor(below / 3)) * 3;
var fives = triangular(Math.floor(below / 5)) * 5;
var fifteens = triangular(Math.floor(below / 15)) * 15;
return threes + fives - fifteens;
}

Tim

[SiliconWizard]

Yes, that's basically how I handled it. Just use the well known sum of the series 1+...+n and factor things. I was using Calc (the "C-style arbitrary precision calculator") and introduced a stupid typo I couldn't immediately spot. That happens...

[westfw]

For an "embedded systems" interview , consider the "obvious" C implementation:

Code: [Select]

long summultiples(long below)
{
    long i, sum=0;
    for (i=3; i < below; i+=3)
    sum += i;
    for (i=5; i < below; i+=5)
    sum += i;
    for (i=15; i < below; i+=15)
    sum -= i;
    return sum;
}

• Is the code smaller or larger than Tim's "obviously better" algorithm?  How much?  What about on a Cortex-M0 with no division instruction?  What about on an 8bit CPU with no multiple OR divide?
• How slow is it?  O(n), right?  Whereas without multiply/divide, it's more like O(32) (assuming 32bit math.)  But the constants in the actual timing get pretty significant.  Approximately what value of N is the crossover?  (pick an architecture with no divide or multiply...)

[T3sl4co1l]

Well the divisions don't matter, they are by constants so can be transformed to clever multiplications by a sufficiently clever compiler.

Offhand, for the AVR instruction set I'm familiar with (8 bit, 8x8 mul), you'd expect... well heck, with longs all over, that's a 4-byte access for basically every statement, that's a big stinker right there.  Not a great example.  Well, er, if we stick with the minimum required for the problem as given (1000 requires just a little over 8 bits, so we should use uint16_t's), we need about 9 cycles per loop, plus some overhead per loop, and times three loops.  For argument's sake, let's say cycles = 3 * (9n + 4) + 17.  In comparison, the given method would incur about 40 cycles for the multiply (maybe a bit pessimistic, including call overhead?), so it doesn't take much N to be worth being clever (~9?).

And then for ARM, M0, it'll probably be about a cycle per instruction, and just a handful of cycles (3-5?) per loop, versus a 32 or 64 bit long-hand multiply -- which if it's one bit per cycle algorithm, will take quite a few cycles to complete, but I think a binary sequence is possible thanks to the one-cycle barrel shifter? are we assuming that's always implemented as well? -- so we'd be looking at >200 cycles there; but a lot fewer if we limit it to the 16-bit requirement (or for that matter, we can stop the long-multiply algorithm at the known required 10 bit level; or 9 bits even?).

If we inspect the overall expression (I didn't before, out of laziness), we can collect the N^2's together with a coefficient of (1/a + 1/b - 1/ab)/2, and the N's sum to just N/2.  a and b are known at compile time so the coefficient is as well, and the N*N*coefficient can be expressed as a triple product using at most... six? multiplies.  So the AVR (16 bit precision) is probably closer to 120 cycles (flat), in this case.  Which isn't that far off from the no-multiply ARM actually, interestingly enough (granted, the ARM likely can run faster; well, huh, if it's so basic it doesn't have mul, it might not even capable of 60MHz?).


I was tempted to write a variadic function, or, well I wouldn't do that honestly, but just supply an array of factors to test, but same idea since, variable length arrays in JS.  Anyway, that would require resolving the correct combination of factors (easy for two prime factors, as seen above; but what about others?), and also accounting for common factors (coprimality).  So there may end up being some factorization required, which would be dumb.  Maybe that's not necessary, I'd have to un-lazily think about it a little bit.  If coprimality doesn't matter, then it should suffice to subtract all composite terms, and there you have it; easily looped over.  The result would be O(number of factors) I think?

Tim

[westfw]

a 4-byte access for basically every statement, that's a big stinker right there.

Well, yeah.  But summultiples(1000) doesn't fit in 16bits...

divisions don't matter, they are by constants so can be transformed to clever multiplications by a sufficiently clever compiler.

That'd be nice.  It doesn't seem to happen with either the ARM or AVR gcc compilers, though.  At least, not for 3, 5, and 15.

Here are the size results for AVR, CM4, CM0.   They're "somewhat interesting."

WWMac<6115> # AVR without Multiply instruction
WWMac<6116> avr-gcc -mmcu=attiny84 -Os -nostartfiles prob1.c -DFASTALG=0
WWMac<6117> size a.out
   text    data     bss     dec     hex filename
    242       0       4     246      f6 a.out
WWMac<6118> avr-gcc -mmcu=attiny84 -Os -nostartfiles prob1.c -DFASTALG=1
WWMac<6119> size a.out
   text    data     bss     dec     hex filename
    618       0       4     622     26e a.out

(OK, that's pretty dramatic.)


WWMac<6120> # AVR with multiply instructon
WWMac<6121> avr-gcc -mmcu=atmega328 -Os -nostartfiles prob1.c -DFASTALG=0
WWMac<6122> size a.out
   text    data     bss     dec     hex filename
    244       0       4     248      f8 a.out
WWMac<6123> avr-gcc -mmcu=atmega328 -Os -nostartfiles prob1.c -DFASTALG=1
WWMac<6124> size a.out
   text    data     bss     dec     hex filename
    650       0       4     654     28e a.out

(Interesting - I wasn't expecting it to be bigger.  Much faster, probably, using 8bit multiplies to do 32bit multiplication, but not as tight a loop.)

WWMac<6125> # ARM CM4
WWMac<6126> /usr/local/gcc-arm7-2018-q2u2/bin/arm-none-eabi-gcc -mcpu=cortex-m4 -mthumb -g -Os -nostartfiles prob1.c -DFASTALG=0
WWMac<6127> size a.out
   text    data     bss     dec     hex filename
     76       0       4      80      50 a.out
WWMac<6128> /usr/local/gcc-arm7-2018-q2u2/bin/arm-none-eabi-gcc -mcpu=cortex-m4 -mthumb -g -Os -nostartfiles prob1.c -DFASTALG=1
WWMac<6129> size a.out
   text    data     bss     dec     hex filename
    108       0       4     112      70 a.out

(This is more like it!)


WWMac<6130> # ARM CM0plus
WWMac<6131> /usr/local/gcc-arm7-2018-q2u2/bin/arm-none-eabi-gcc -mcpu=cortex-m0plus -mthumb -g -Os -nostartfiles prob1.c -DFASTALG=0
WWMac<6132> size a.out
   text    data     bss     dec     hex filename
     76       0       4      80      50 a.out
WWMac<6133> /usr/local/gcc-arm7-2018-q2u2/bin/arm-none-eabi-gcc -mcpu=cortex-m0plus -mthumb -g -Os -nostartfiles prob1.c -DFASTALG=1
WWMac<6134> size a.out
   text    data     bss     dec     hex filename
    600       0       4     604     25c a.out

(holy crap.  I knew there was some "not optimized" code in the CM0, but I thought it was mostly off in the floating point code.  But here, the 32bit divide function is really 460 bytes long!)

[westfw]

divisions  can be transformed to clever multiplications

That'd be nice.  It doesn't seem to happen with either the ARM or AVR gcc compilers, though.

Ah.  the ARM gcc DOES do this on the m4 (where it barely matters.)But not on the M0plus.  Presumably it's upset that there is no 32*32->64bit multiply.  Hmmph.


The division routine is well unrolled, presumably for performance (but I wouldn't want to predict how it interacts with typical m0/m0+ flash memory systems.)  I'm sure it's all swell if you're running on one of the chips with 128k+ of flash, but perhaps not so much on those 4k chips "they" are trying to push on the 8bit users.  :-(gcclib does have separate code for __OPTIMIZE_SIZE__, but I don't know if anyone is distributing binaries that use that.(huh.  Arduino does.  Using the Arduino ARM compiler distribution, size for the M0 shrinks to 324 bytes total, with a 172byte division function.)