Log Transformations for efficient multiplication between lots of positive numbers [Technique Tuesdays]
This is a technique you will see all kinds of fields.
To learn more about the newsletter, check our detailed About Page + FAQs
To help me understand you better, please fill out this anonymous, 2-min survey. If you liked this post, make sure you hit the heart icon in this email.
Recommend this publication to Substack over here
Take the next step by subscribing here
Here is a fun question for you,
How would you handle the multiplication of several very large numbers? Let’s say you had to multiply 100 numbers (each over 10000) with each other. This can cause memory if you just tried to use the standard method. What would you do?
Or what about the opposite case? Imagine multiplying a hundred positive numbers, each less than 1? What could you do then? You’ll notice that your computer’s precision will break very quickly, and you will end up with 0. How would you ensure that you don’t lose this computation?
You could create/use a data structure that handles numbers with these many decimal places. However, this requires a lot of memory. If you’re designing systems that need to operate at very large scales (think Facebook, Google, etc) or systems with limited computational power (embedded systems), then this might not be practical. There is a better way. We can use some clever math to make our lives much better.
Key Highlights
The Technique- Let’s say you have a list of numbers n and you want the product of all the terms. You take the log of the product. This converts the problem into the addition of the logs of both numbers, which makes it much more manageable.
The Math- To those of you that want to look at the equations-
product= list[0]*list[1] *...list[n-1] => log(product)= log(list[0]*list[1] *...list[n-1]) = log(list[0])+ log(list[1])+ ...log(list[n-1])#product law of logs. We can use the log of the products for our computations
Why this works- Logs have interesting behaviors.
For small positive numbers (<1)- The log of a number is bigger than the number.
For Large Numbers- The log of the number is smaller than it.
This allows us to handle the precision and memory overflow very well. The addition of small numbers will not hit 0 the way multiplying them would. Multiplication of large numbers will not overflow as quickly as their multiplication.
But aren’t we using different numbers- Some of you might be concerned about using the log of the product instead of the product since they are different numbers. And this is a valid concern. However, keep in mind that all of the calculations just represent ideas in the end. As long as you build your system to account for this tweak, there is no problem.
You will this technique all the time, especially in domains like AI, Big Data, and Machine Learning where you have a lot of computations. To see some examples of it being used in Machine Learning, watch the video below.
I created Technology Interviews Made Simple using new techniques discovered through tutoring multiple people into top tech firms. The newsletter is designed to help you succeed, saving you from hours wasted on the Leetcode grind. I have a 100% satisfaction policy, so you can try it out at no risk to you. You can read the FAQs and find out more here. Use the button below to get 20% off for upto a whole year.
Before proceeding, if you have enjoyed this post so far, please make sure you like it (the little heart button in the email/post). I also have a special request for you.
***Special Request***
This newsletter has received a lot of love. If you haven’t already, I would really appreciate it if you could take 5 seconds to let Substack know that they should feature this publication on their pages. This will allow more people to see the newsletter.
There is a simple form in Substack that you can fill up for it. Here it is. Thank you.
https://docs.google.com/forms/d/e/1FAIpQLScs-yyToUvWUXIUuIfxz17dmZfzpNp5g7Gw7JUgzbFEhSxsvw/viewform
To get your Substack URL, follow the following steps-
Open - https://substack.com/
If you haven’t already, log in with your email.
In the top right corner, you will see your icon. Click on it. You will see the drop-down. Click on your name/profile. That will show you the link.
You will be redirected to your URL. Please put that in to the survey. Appreciate your help.
In the comments below, share what topic you want to focus on. I’d be interested in learning and will cover them. To learn more about the newsletter, check our detailed About Page + FAQs
If you liked this post, make sure you fill out this survey. It’s anonymous and will take 2 minutes of your time. It will help me understand you better, allowing for better content.
https://forms.gle/XfTXSjnC8W2wR9qT9
I see you living the dream.
Go kill all and Stay Woke,
Devansh <3
To make sure you get the most out of Technique Tuesdays, make sure you’re checking in the rest of the days as well. Leverage all the techniques I have discovered through my successful tutoring to easily succeed in your interviews and save your time and energy by joining the premium subscribers down below. Get a discount (for a whole year) using the button below
Reach out to me on:
Instagram: https://www.instagram.com/iseethings404/
Message me on Twitter: https://twitter.com/Machine01776819
My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/
My content:
Read my Machine Learning breakdowns: https://rb.gy/zn1aiu
My YouTube: https://rb.gy/88iwdd
Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75