Connexion
There are many algorithms for which it has been mathematically proven that a quantum computer can generate results that would take a classical computer an unreasonable amount of time to generate. Unfortunately, today's quantum computers either can't run those algorithms or can only run simplified versions that classical computers can also handle. This has left the field facing a challenging question: Can we demonstrate the promise of quantum computers on today's noisy, limited hardware?
That's a more difficult question than it may first appear. If you generate a result that's out of reach of today's regular computers, it may not be possible to verify that you got the right result. And given that today's quantum computers are somewhat error-prone, getting the wrong result is a distinct possibility. Further, in the absence of a mathematical proof of the capabilities of quantum hardware, it's possible that a better classical algorithm could outperform the quantum hardware.
These issues inspired IBM to launch a quantum advantage tracker. On Thursday, the company announced three new entries that it says clearly show a quantum advantage, each using a different approach to overcoming errors and validating quantum results. "Trusted computing when you can do classical simulations is irrelevant," IBM's Jay Gambetta told Ars. "Trusted computing when you can't do classical simulations is a big deal."
Threads has passed 500 million monthly active users as Meta expands Communities and rolls out Your Algo feed controls in the US, UK, Canada, Australia, and New Zealand.
The post Meta’s Threads Hits 500 Million Users, Adds New Personalization Tools appeared first on TechRepublic.
Pilots’ voices from the last seconds of a fatal cargo plane crash have been re-created by Internet sleuths using software and AI tools. The spread of reconstructed audio recordings has prompted a US government agency to suspend all public access to its database of civil transportation accidents—because federal law prohibits investigators from publicly releasing audio from cockpit voice recorders.
The US National Transportation Safety Board (NTSB) usually shares factual reports and evidence gathered from investigations of aircraft crashes and other civil transportation incidents. But on May 21, the NTSB announced that the online docket system containing such information was “temporarily unavailable” as it reviewed the publicly available materials that had enabled people to re-create cockpit audio recordings from aircraft disasters.
“The NTSB is aware that advances in image recognition and computational methods have enabled individuals to reconstruct approximations of cockpit voice recorder audio from sound spectrum imagery released as part of NTSB investigations, including the ongoing investigation of the crash last year of UPS flight 2976 in Louisville, Kentucky,” according to an NTSB statement. “The NTSB does not release cockpit audio recordings.”
In this post we’re going to study the third-grade algorithm to compute the product of two numbers, and we’re going to compare it with a much more efficient algorithm: The Karatsuba multiplication algorithm.
Did you know that these two algorithms are the ones used in the built in Python multiplication?
We will talk about the Order of both algorithms and give you Python implementations of both of them.
Maybe you’re thinking, why is she writing now about algorithms? Some time ago, I took the course Algorithms: Design and Analysis, Part 1&2, by Tim Roughgarden, and it was a lot of fun.
Now I’m taking the course again, but I’m spending more time to review the algorithms and play with them. I really encourage you to take the course if you have some time. But first, read this post 
This is the outline:
Let’s start!
First, we’re going to review the third grade algorithm, which all of you already know
Let’s start with these two numbers: 5678 x 1234. In order to compute their product you start with 4*5678, represented as:
(2)(3)(3) 5 6 7 8 x 1 2 3 |4| ------------- 2 2 7 1 2
Let’s count the number of operations performed in this step:
– If n is the number of digits of the first number, there are n products and at most n sums (carried numbers).
– So in total, you need 2n operations.
If we continue with the product, we have to repeat n times the same operation (where we assume that n is also the number of digits of the second number):
Lateo.net - Flux RSS en pagaille (pour en ajouter : @ moi) 5 6 7 8
x 1 2 3 4
-------------
2 2 7 1 2
1 7 0 3 4
1 1 3 5 6
5 6 7 8
which gives a total of 2n2 operations.
Finally, you need to sum all these numbers,
5 6 7 8
x 1 2 3 4
-------------
2 2 7 1 2
1 7 0 3 4
1 1 3 5 6
+ 5 6 7 8
----------------------
7 0 0 6 6 5 2
which takes around n2 operations more.
So in total, the number of operations is ~3n2, which means that it’s quadratic with the input (proportional to n2).
One point I would like to mention about this algorithm is that it’s complete: no matter what x and y you start with, if you perform correctly the algorithm, the algorithm terminates and finds the correct solution.
Here I give you an example of an implementation of the third grade algorithm, where I have included a Counter for the sum and product operations:
# third_grade_algorithm.py
def counted(fn):
# Counter Decorator
def wrapper(*args, **kwargs):
if "" in args or " " in args:
return "".join(map(lambda s: s.strip(), args))
wrapper.called += 1
return fn(*args, **kwargs)
wrapper.called = 0
wrapper.__name__ = fn.__name__
return wrapper
@counted
def prod(x, y):
# x, y are strings --> returns a string of x*y
return str(eval("%s * %s" % (x, y)))
@counted
def suma(x, y):
# x, y are strings --> returns a string of x+y
return str(eval("%s + %s" % (x, y)))
def one_to_n_product(d, x):
"""d is a single digit, x is n-digit --> returns a string of d*x
"""
result = ""
carry = "0"
for i, digit in enumerate(reversed(x)):
r = suma(prod(d, digit), carry)
carry, digit = r[:-1], r[-1]
result = digit + result
return carry + result
def sum_middle_products(middle_products):
# middle_products is a list of strings --> returns a string
max_length = max([len(md) for md in middle_products])
for i, md in enumerate(middle_products):
middle_products[i] = " " * (max_length - len(md)) + md
carry = "0"
result = ""
for i in range(1, max_length + 1):
row = [carry] + [md[-i] for md in middle_products]
r = reduce(suma, row)
carry, digit = r[:-1], r[-1]
result = digit + result
return carry + result
def algorithm(x, y):
# x, y are integers --> returns an integer, x*y
x, y = str(x), str(y)
middle_products = []
for i, digit in enumerate(reversed(y)):
middle_products.append(one_to_n_product(digit, x) + " " * i)
return int(sum_middle_products(middle_products))
Using that algorithm, if you run
$ python -i third_grade_algorithm.py
where (third_grade_algorithm.py is the name of the file), you will run the previous code and terminate with the Python console open. This way you can call your algorithm function and try:
>>> algorithm(6885, 1600)
1101600
>>> print("Suma was called %i times" % suma.called)
Suma was called 20 times
>>> print("Prod was called %i times" % prod.called)
Prod was called 16 times
So it took 20 + 16 = 36 operations to compute the product of these two numbers.
Once we have this code, we can average the number of operations used in the product of n-digit numbers:
def random_prod(n):
suma.called = 0
prod.called = 0
x = randint(pow(10, n - 1), pow(10, n))
y = randint(pow(10, n - 1), pow(10, n))
algorithm(str(x), str(y))
return suma.called + prod.called
def average():
ntimes = 200
nmax = 10
result = []
for n in range(nmax):
avg = sum([random_prod(n + 1) for i in range(ntimes)]) / float(ntimes)
result.append([n + 1, avg])
return result
In the following figure, we plot the result of the previous experiment when ntimes = 200 samples and nmax = 10 digits:
We can see that these points fit the curve f(n) = 2.7 n2.
Note that 2.7 < 3, the proportionality factor we deduced before. This is because we were assuming the worst case scenario, whereas the average product takes into account random numbers.
But can we do better? Is there an algorithm that performs the product of two numbers quicker?
The answer is yes, and in the following section we will study one of them: The Karatsuba Algorithm.
Let’s first explain this algorithm through an example:
Imagine you want to compute again the product of these two numbers:
x = 5678 y = 1234
In order to do so, we will first decompose them in a singular way:
x = 5678 a = 56; b = 78 --> x = 100 * a + b
and the same for y:
y = 1234 c = 12; d = 34 --> y = 100 * c + d
If we want to know the product x * y:
xy = (100 * a + b)(100 * c + d) = 100^2 * ac + 100 * (ad + bc) + bd
Where we can calculate the following 3 parts separately:
A = ac B = ad + bc C = bd
However, we need two compute two products for the B term. Let’s see how we can compute only one product to reduce calculations
If we expand the product:
D = (a+b) * (c+d) = ac + ad + bc + bd
we see than the right hand side of the equation contains all A,B and C terms.
In particular, if we isolate B = ad + bc, we get:
B = D - ac - bd = D - A - C
Great! Now we only need three smaller products in order to compute x * y:
xy = 100^2 A + 100(D - A - C) + C A = ac B = (a+b)(c+d) C = bd
Let’s put some numbers into the previous expressions:
xy = 100^2 * A + 100 * (D - A - C) + C A = ac = 56 * 12 = 672 C = bd = 78 * 34 = 2652 D = (a+b)(c+d) = (56 + 78)(12 + 34) = 134 * 46 = 6164 xy = 100^2 * 672 + 100 * (6164 - 672 - 2652) + 2652 = 6720000 + 284000 + 2652 = 7006652
Yes! the result of 1234 * 5678 = 7006652!
In the next section, we’ll see the pseudo code for the Karatsuba Algorithm and we’re going to translate it into Python code.
In general though, we don’t have 4-digit numbers but n-digit numbers. In that case, the decomposition to be made is:
x = n-digit number m = n/2 if n is even m = (n+1)/2 if n is odd a = 10^m * x1 + x2 --> x1 = First (n-m) digits of x --> x2 = Last m digits of x
which is slightly different if n is even or odd.
In pseudocode, the Karatsuba Algorithm is:
procedure karatsuba(x, y)
/* Base Case */
if (x < 10) or (y < 10)
return x*y
/* calculates the number of digits of the numbers */
m = max(size_base10(x), size_base10(y))
m2 = m/2
/* split the digit sequences about the middle */
a, b = split_at(x, m2)
c, d = split_at(y, m2)
/* 3 products of numbers with half the size */
A = karatsuba(a, c)
C = karatsuba(b, d)
D = karatsuba(a+b, c+d)
return A*10^(2*m2) + (D-A-C)*10^(m2) + C
And the order of this algorithm Ο(nlog23) ≈ Ο(n1.585) is (more info).
Let’s write now the Python code
def karatsuba(x, y):
# Base case
if x < 10 or y < 10:
return x * y
# Calculate the number of digits of the numbers
sx, sy = str(x), str(y)
m2 = max(len(sx), len(sy)) / 2
# Split the digit sequences about the middle
ix, iy = len(sx) - m2, len(sy) - m2
a, b = int(sx[:ix]), int(sx[ix:])
c, d = int(sy[:iy]), int(sy[iy:])
# 3 products of numbers with half the size
A = karatsuba(a, c)
C = karatsuba(b, d)
D = karatsuba(a + b, c + d)
return A * 10**(2 * m2) + (D - A - C) * 10**m2 + C
assert(karatsuba(1234, 5678) == 7006652)
Which is much simpler than the third-grade algorithm right?
Moreover, if we can compare the number of calculations of this algorithm with respect to the third-grade one:
where the red line is the Karatsuba algorithm, and the blue lines the 3rd grade one (see above).
Finally, I want to write here one of the quotes mentioned in the Algorithms course, which might encourage you to find a better solution
The post 3rd-grade & Karatsuba multiplication Algorithms appeared first on Marina Mele's site.
At Raspberry Pi, we’re interested in all things to do with technology, from building new tools and helping people teach computing, to researching how young people learn to create with technology and thinking about the role tech plays in our lives and society. One of the aspects of technology I myself have been thinking about recently is algorithms.
Technology impacts our lives at the level of privacy, culture, law, environment, and ethics.
All kinds of algorithms — set series of repeatable steps that computers follow to perform a task — are running in the background of our lives. Some we recognise and interact with every day, such as online search engines or navigation systems; others operate unseen and are rarely directly experienced. We let algorithms make decisions that impact our lives in both large and small ways. As such, I think we need to consider the ethics behind them.
Ethics are rules of conduct that are recognised as acceptable or good by society. It’s easier to discuss the ethics of a specific algorithm than to talk about ethics of algorithms as a whole. Nevertheless, it is important that we have these conversations, especially because people often see computers as ‘magic boxes’: you push a button and something magically comes out of the box, without any possibility of human influence over what that output is. This view puts power solely in the hands of the creators of the computing technology you’re using, and it isn’t guaranteed that these people have your best interests at heart or are motivated to behave ethically when designing the technology.
Who creates the algorithms you use, and what are their motivations?
You should be critical of the output algorithms deliver to you, and if you have questions about possible flaws in an algorithm, you should not discount these as mere worries. Such questions could include:
Below, I give two concrete examples to show where ethics come into the creation and use of algorithms. If you know other examples (or counter-examples, feel free to disagree with me), please share them in the comments.
Part of the ‘magic box’ mental model is the idea that computers are cold instructions followers that cannot think for themselves — so how can they be biased?
Humans aren’t born biased: we learn biases alongside everything else, as we watch the way our family and other people close to us interact with the world. Algorithms acquire biases in the same way: the developers who create them might inadvertently add their own biases.
Humans can be biased, and therefore the algorithms they create can be biased too.
An example of this is a gang violence data analysis tool that the Met Police in London launched in 2012. Called the gang matrix, the tool held the personal information of over 300 individuals. 72% of the individuals on the matrix were non-white, and some had never committed a violent crime. In response to this, Amnesty International filed a complaint stating that the makeup of the gang matrix was influenced by police officers disproportionately labelling crimes committed by non-white individuals as gang-related.
We live in a content-rich society: there is much, much more online content than one person could possibly take in. Almost every piece of content we consume is selected by algorithms; the music you listen to, the videos you watch, the articles you read, and even the products you buy.
Some of you may have experienced a week in January of 2012 in which you saw a lot of either cute kittens or sad images on Facebook; if so, you may have been involved in a global social experiment that Facebook engineers performed on 600,000 of its users without their consent. Some of these users were shown overwhelmingly positive content, and others overwhelmingly negative content. The Facebook engineers monitored the users’ actions to gage how they responded. Was this experiment ethical?
In order to select content that is attractive to you, content algorithms observe the choices you make and the content you consume. The most effective algorithms give you more of the same content, with slight variation. How does this impact our beliefs and views? How do we broaden our horizons?
People generally don’t like making decisions; almost everyone knows the discomfort of indecision. In addition, emotions have a huge effect on the decisions humans make moment to moment. Algorithms on the other hand aren’t impacted by emotions, and they can’t be indecisive.
While algorithms are not immune to bias, in general they are way less susceptible to it than humans. And if a bias is identified in an algorithm, an engineer can remove the bias by editing the algorithm or changing the dataset the algorithm uses. The same cannot be said for human biases, which are often deeply ingrained and widespread in society.
As is true for all technology, algorithms can create new problems as well as solve existing problems.
That’s why there are more and less appropriate areas for algorithms to operate in. For example, using algorithms in policing is almost always a bad idea, as the data involved is recorded by humans and is very subjective. In objective, data-driven fields, on the other hand, algorithms have been employed very successfully, such as diagnostic algorithms in medicine.
I would love to hear what you think: this conversation requires as many views as possible to be productive. Share your thoughts on the topic in the comments! Here are some more questions to get you thinking:
Feel free to respond to other people’s comments and discuss the points they raise.
The ethics of algorithms is one of the topics for which we offer you a discussion forum on our free online course Impact of Technology. The course also covers how to facilitate classroom discussions about technology — if you’re an educator teaching computing or computer science, it is a great resource for you!
The Impact of Technology online course is one of many courses developed by us with support from Google.
The post Can algorithms be unethical? appeared first on Raspberry Pi.
