Ok, maybe I don't understand the problem, but it seems obvious that it should never be greater than O(min(n1, n2) * 10), where n1 and n2 are the lengths in digits of each argument, and assuming we are multiplying decimal numbers.
Take the first digit of the longer number. Multiply it by the shorter number and store the result. Take the second digit of the longer number. If it matches the first digit, do a lookup of the last result and use that, else multiply and store. Repeat.
There will be a maximum of 10 * (length of the shorter number) multiplies, because there are only 10 unique digits. After that every operation is a lookup.
You could even do a tiny optimization by skipping the multiplication for the zero digit.
Worst case, the two numbers are the same length, in which case it's O(n/2 * 10), which is a heck of a lot better than O(n log n).
What am I missing here?
EDIT to respond to the comments: in the article, they are only counting the number of multiplies in the O() value. They are not including the adds.
> EDIT to respond to the comments: in the article, they are only counting the number of multiplies in the O() value. They are not including the adds.
This simplification relies on the fact that after making a multiplication the cost of merging it with the result of another is always less than the cost of performing the multiplication, so it doesn't change the overall complexity.
This is not true in your proposed algorithm: a lookup is O(1), but merging is O(N), so you cannot do the same simplification and have to count the complexity of performing adds as well.
By your reasoning, multiplying two numbers in binary involves no multiplication at all, because multiplying by 1 and multiplying by 0 are both trivial operations.
But obviously multiplying two n-bit binary numbers is not done in O(1) time, so "only counting the number of multiplies" is not a meaningful model, and not the model adopted by the researchers quoted in the article.
The final time complexity for Karatsubas does account for the addition via the master theorem and gives you something less than n^2. It’s just in some sense the recursion is dominant so we add to the exponent. As a result, I think the article is just talking about counting multiplications since it’s in some sense the “expensive” operation in the both the recursive karatsuba and the regular grade school method.
The reason the adds don't count is not because they arbitrarily decided to ignore them.
Addition is O(n), multiplication is more than O(n), by the nature of the big-O notation, when you have to do a series of operation, you only have to count the ones with the highest complexity. So in the Karatsuba example where the formula involves both additions and (recursive) multiplications, the additions don't count only because the multiplications dominate.
Or, as a formula, O(n log n) + O(n) = O(n log n), and btw O(n/2*10) = O(n), in big-O, constant factors don't count
Not an expert, but I think the algorithm works for any base, not just 10. The python implementation uses base 2^30 for their multiplication. Base 10 is just a convenient illustration
Once the longer number starts repeating digits, then it's not n^2 anymore. Multiplies get replaced with lookups. And we're only counting the multiplies. That's all they counted in the article. Not the adds, not the shifts.
They don't count the additions or shifts because they're both linear time operations, and thus provably at least as fast as multiplication (both in an asymptotic and exact sense). In any case where multiplication is super-linear, this means that addition and shifting are are not the temporal bottleneck at any stage in the algorithm where you have a constant number of those operations surrounding at least one multiplicative recursive call (on numbers of similar magnitudes).
If additions were truly free, an even easier optimal algorithm would just be repeated addition involving zero multiplications.
The complexity of Karatsuba's algorithm, because it's a recursive one that gets "wider" at every level, is dominated by the width of that recursion. The top level always has a small number of operations, so we don't explicitly count them there, but the bottom has the truly huge number of operations that contribute to the algorithm's complexity, because each level of recursion dramatically increases the number of operations. Some number of those operations (most of them, in fact) will be single-digit additions.
Memoizing number-by-digit multiplication doesn't make multiplication O(1) because one must still do an N-digit addition (which is O(N)) for each digit.
That's not recursion. And reversing arrows on this category turns base cases into co-base, or start cases, (and these are still often called base cases in the literature), so it is still required.
Reversing arrows again, back to recursion, you have exactly the standard labeled bases case (well, cases in your code), and reversing arrows doesn't magically change algorithms or invent new structure, so it completely equivalent in the category.
For that code, the 1:1:... is exactly the terminating/starting point, reversing arrows in the category does nothing to change the requirements.
But the author of that page is not concerned with readability or accessibility. He just wants things to look cool and design-y. One piece of supporting evidence he cites is some random photo he took that doesn't contain #000000 black. That doesn't mean anything, it could be that it's over-exposed, or has poor contrast, or had some silly filter applied. This leads me to think that the author of that page doesn't know what he's talking about.
So you routinely encounter photographs that have noticable areas where sensor did not receive any light during exposure? To the point where you feel not having completely unlit parts of a photo is a sign of over-exposure or filters? Are you an astrophotographer?
Wow, I was searching for this exact link for more than a decade (!). I remember seeing it on HN when I was new here and couldn't find the article ever again. Thanks for sharing!
It's not clear to me whether Anthropic's limitations are technical or merely contractual. Is Anthropic actually putting the limitations in their prompts, so that the model would refuse to answer a question on how to do certain things?
If so, that's a major problem. If the military is using it in some mission critical way, they can't be fighting the model to get something done. No such limitations would ever be acceptable.
If the limitations are contractual, then there is some room for negotiation.
> If the military is using it in some mission critical way, they can't be fighting the model to get something done. No such limitations would ever be acceptable.
You'd be surprised at what is considered acceptable. For example, being unable to repair your own equipment in battle is considered acceptable by decision-makers who accepted the restrictions.
This looks great, but it's not clear to me how to use it for a practical task. I need to transcribe about 10 years worth of monthly meetings. These are government hearings with a variety of speakers. All the videos are on YouTube. What's the most practical and cost-effective way to get reasonably accurate transcripts?
In the api it took 18s to do a 20m audio file I had lying around where someone is reviewing a product.
There will, I'm sure, be ways of running this locally up and available soon (if they aren't in huggingface right now) but the API is $0.003/min. If it's something like 120 meetings (10 years of monthly ones) then it's roughly $20 if the meetings are 1hr each. Depending on whether they're 1 or 10 hours (or if they're weekly or monthly but 10 parallel sessions or something) then this might be a price you're willing to pay if you get the results back in an afternoon.
edit - their realtime model can be run with vllm, the batch model is not open
if it's 1 monthly video and thus 120 videos (or so) you could try recall (getrecall.ai not recall.ai that is a similar product with a similar name). They summarize youtube videos, but you get the transcript. AFAIK you cannot batch the processing and you have to add each video one by one, that's why 100 or 200 videos is doable but probably not thousands.
Irked me too. I'm running for state representative in House District 9, which covers much of that area. The district is drop dead gorgeous and it's growing rapidly. There's a lot here.
Pretty much everyone on earth is proud of their home area. I've never really been to a place where people didn't describe their home as one of the most beautiful places on earth.
Earth has a lot of nice places. The flatness of Indiana can be calming and beautiful. But if you're driving on main roads, it's not very exciting, and it's not the kind of exciting people will fly across the world to see. And that was the point in the article.
I love my home town. I grew up there, and it was fine. I would never describe it as one of the most beautiful places on earth. I'm I proud of it? Only in the sense it's home and I have family there.
People do fly out to vacation in the part of Indiana he highlighted!
I'm not saying Indiana on the whole isn't flat. When I was growing up, their ad campaign was literally "there's more than corn in Indiana". I'm just saying, he couldn't have picked a worse map location to make the point with.
Many areas have some minor hills, or some variant infinitely more interesting (hoosier myself, I regret moving here 10 years ago and may finally be bothered enough by it to deal with moving out in Spring). All in all, a state this big with less than 1,000 ft between the highest and lowest parts is just disappointingly flat, given the general lack of other natural attraction.
I'd say the caves in that region of the state are interesting, but options like Mammoth Cave are not that far away in KY (and they have better hills too).
178 billion? That's nothing. I did trillions just this morning. I went to the grocery store and picked an item off the shelf, effectively filtering out the trillions of other products that I could have picked but didn't.
They did not process 178 billion rows per second. They did a search that found something in a large data set by eliminating the parts of the data set that could not have contained the item. Same way I did by picking one grocery store and going straight to the shelf.
Hm, if I understand their product correctly they are building a DB and their filtering actually returns correct results.
So, the analogy doesn't really hold true unless you actually have these trillions of alternate products stored in your brain and manage to cite the matching subset on demand.
If you can't afford your taxes your business model was flawed to begin with. In the above example there is more than enough money for it to still be worth doing.
You don't seem to understand the implications here. This requires bootstrapped startups to have gross margins substantially above incumbents in order to compete and not be cash flow negative after paying taxes.
It makes it substantially more cashflow intensive to build a new software business, which entrenches incumbents and reduces competition. It favors companies who have the cash to wait for the full 5-year depreciation cycle, i.e. the opposite of most bootstrapped startups.
Quick example:
$10,000 revenue
$8,000 paid to software developer
$1,000 paid to AWS
leaves $1000 in profit.
You received $10,000 into your business account, but spent 8000+1000 = $9000. Your business account has a balance of $1000 at the end of the year.
Section 174 means you can only deduct 1/10th of the $8000 in the first year, $800. Your total deductible business expenses for the year will be 800+1000 = $1800.
Your taxable profit for the year is 10000-1800 = $8,200. If your effective tax rate is 25% (generously low), you owe $2,050 in taxes.
You pay your $2,050 tax payment and your business account is overdrafted by $1,050. You need to add $1,050 from your personal funds to the business to cover the shortfall.
Your business was cash flow negative for the year. This makes it extremely difficult to bootstrap a software company.
Well, I said elsewhere, this effectively means (heavily) taxing anyone who's doing something new (meaning adding additional taxes on top of income tax). Essentially all of Europe does this, and people here often decry how they totally lack innovation across the entire continent.
I don't think these two are unrelated.
I also don't understand the objection. It's not like anyone's getting away from taxes due to this rule. This is about a temporary exemption from company income tax IF AND ONLY IF companies have someone pay income tax on that money (and only up to the point where that keeps makes sense). This "exemption" lets you not add 15%-20% tax on top of 40-55% income tax just to try a new business as a company.
Basically think mixture of experts, but each expert is an encoder with it's own input tokenization/feature engineering part and then there is some machinery to parametrize these encoders based on natural language queries and stitch their outputs together to form unified vectors for objects in the index and the queries coming in.
We have some proprietary tech besides that - mainly embedding models for things like location and then executors for the Superlinked DAG that help you run it on GPU-accelerated Spark and something analogous to that for streaming workloads - those proprietary things are how we make money, we call it Superlinked Cloud.
Take the first digit of the longer number. Multiply it by the shorter number and store the result. Take the second digit of the longer number. If it matches the first digit, do a lookup of the last result and use that, else multiply and store. Repeat.
There will be a maximum of 10 * (length of the shorter number) multiplies, because there are only 10 unique digits. After that every operation is a lookup.
You could even do a tiny optimization by skipping the multiplication for the zero digit.
Worst case, the two numbers are the same length, in which case it's O(n/2 * 10), which is a heck of a lot better than O(n log n).
What am I missing here?
EDIT to respond to the comments: in the article, they are only counting the number of multiplies in the O() value. They are not including the adds.