Daniel Lemire's blog
A simple algorithm to compute the square root of an integer, byte by byte
A reader asked me for some help in computing (1 – sqrt(0.5)) to an arbitrary precision, from scratch. A simpler but equivalent problem is to compute the square root of an integer (e.g., 2). There are many sophisticated algorithms for such problems, but we want something relatively simple. We’d like to compute the square root bit by bit…
For example, the square root of two is…
1. 5 / 4
2. 11 / 8
3. 22 / 16
4. 45 / 32
5. 90 / 64
6. 181 / 128
7. …
More practically, 8-bit by 8-bit, we may want to compute it byte by byte…
1. 362 / 256
2. 92681 / 65536
3. 23726566 / 16777216
4. …
How can we do so?
Intuitively, you could compute the integer part of the answer by starting with 0 and incrementing a counter like so:
Indeed, the square of the integer part cannot be larger than the desired power.
You can repeat the same idea with the fractional part… writing the answer as x1+x2/B+... smaller terms.
It will work, but it involves squaring ever larger numbers. That is inefficient.
We don’t actually need to compute powers when iterating. If you need to compute x**2, (x+1)**2, (x+2)**2, etc. You can instead use a recursion: if you have computed (x+n)**2 and you need the next power, you just need to add 2(x+n) + 1
because that’s the value of (x+n+1)**2 – (x+n)**2.
Finally, we get the following routine (written in Python). I left the asserts in place to make the code easier to understand:
The algorithm could be further optimized if you needed more efficiency. Importantly, it is assumed that the basis is not too large otherwise another type of algorithm would be preferable. Using 256 is fine, however.
Obviously, one can design a faster algorithm, but this one has the advantage of being nearly trivial.
Further reading: A Spigot-Algorithm for Square-Roots: Explained and Extended by Mayer Goldberg
Credit: Thanks to David Smith for inspiring this blog post.
source
A simple algorithm to compute the square root of an integer, byte by byte
A reader asked me for some help in computing (1 – sqrt(0.5)) to an arbitrary precision, from scratch. A simpler but equivalent problem is to compute the square root of an integer (e.g., 2). There are many sophisticated algorithms for such problems, but we want something relatively simple. We’d like to compute the square root bit by bit…
For example, the square root of two is…
1. 5 / 4
2. 11 / 8
3. 22 / 16
4. 45 / 32
5. 90 / 64
6. 181 / 128
7. …
More practically, 8-bit by 8-bit, we may want to compute it byte by byte…
1. 362 / 256
2. 92681 / 65536
3. 23726566 / 16777216
4. …
How can we do so?
Intuitively, you could compute the integer part of the answer by starting with 0 and incrementing a counter like so:
x1 = 0
while (x1+1)**2 <= M:
x1 += 1
Indeed, the square of the integer part cannot be larger than the desired power.
You can repeat the same idea with the fractional part… writing the answer as x1+x2/B+... smaller terms.
x2 = 0
while (x1*B + x2 + 1)**2 <= M*B**2:
x2 += 1
It will work, but it involves squaring ever larger numbers. That is inefficient.
We don’t actually need to compute powers when iterating. If you need to compute x**2, (x+1)**2, (x+2)**2, etc. You can instead use a recursion: if you have computed (x+n)**2 and you need the next power, you just need to add 2(x+n) + 1
because that’s the value of (x+n+1)**2 – (x+n)**2.
Finally, we get the following routine (written in Python). I left the asserts in place to make the code easier to understand:
B = 2**8 # or any other basis like 2 or 10
x = 0
power = 0
limit = M
for i in range(10): # 10 is the number of digits you want
limit *= B**2
power *= B**2
x*=B
while power + 2*x + 1 <= limit:
power += 2*x + 1
x += 1
assert(x**2 == power)
assert(x**2 <= limit)
# x/B**10 is the desired root The algorithm could be further optimized if you needed more efficiency. Importantly, it is assumed that the basis is not too large otherwise another type of algorithm would be preferable. Using 256 is fine, however.
Obviously, one can design a faster algorithm, but this one has the advantage of being nearly trivial.
Further reading: A Spigot-Algorithm for Square-Roots: Explained and Extended by Mayer Goldberg
Credit: Thanks to David Smith for inspiring this blog post.
source
省流：Neoverse V2
Google Axion Processors – Arm-based CPUs designed for the data center https://cloud.google.com/blog/products/compute/introducing-googles-new-arm-based-cpu/
Google Cloud Blog
Introducing Google’s new Arm-based CPU | Google Cloud Blog
The custom Axion Arm-based processor is designed for general-purpose workloads like web and app servers, databases, analytics, CPU-based AI, and more.
Chips and Cheese
Intel’s Ambitious Meteor Lake iGPU
#ChipAndCheese
Telegraph | source
(author: clamchowder)
Intel’s Ambitious Meteor Lake iGPU
#ChipAndCheese
Telegraph | source
(author: clamchowder)
Arch Linux: Recent news updates
Increasing the default vm.max_map_count value
The vm.max_map_count paramater will be increased from the default
This change should help address performance, crash or start-up issues for a number of memory intensive applications, particularly for (but not limited to) some Windows games played through Wine/Steam Proton. Overall, end users should have a smoother experience out of the box with no expressed concerns about potential downsides in the related proposal on arch-dev-public mailing list.
This
Before upgrading, in case you are already setting your own value for that parameter in a
source
(author: Robin Candau)
Increasing the default vm.max_map_count value
The vm.max_map_count paramater will be increased from the default
65530 value to 1048576.This change should help address performance, crash or start-up issues for a number of memory intensive applications, particularly for (but not limited to) some Windows games played through Wine/Steam Proton. Overall, end users should have a smoother experience out of the box with no expressed concerns about potential downsides in the related proposal on arch-dev-public mailing list.
This
vm.max_map_count increase is introduced in the 2024.04.07-1 release of the filesystem package and will be effective right after the upgrade.Before upgrading, in case you are already setting your own value for that parameter in a
sysctl.d configuration file, either remove it (to switch to the new default value) or make sure your configuration file will be read with a higher priority than the /usr/lib/sysctl.d/10-arch.conf file (to supersede the new default value).source
(author: Robin Candau)
杰哥的{运维，编程，调板子}小笔记
开发一个链接器（3）
前言
这个系列的前两篇博客实现了一个简单的静态链接器，它可以输入若干个 ELF .o 文件，输出 ELF 可执行文件。接下来，我们进一步支持动态库：输入若干个 ELF .o 文件，输出 ELF 动态库。
source
开发一个链接器（3）
前言
这个系列的前两篇博客实现了一个简单的静态链接器，它可以输入若干个 ELF .o 文件，输出 ELF 可执行文件。接下来，我们进一步支持动态库：输入若干个 ELF .o 文件，输出 ELF 动态库。
source
唉原来王羽佳都已经37岁了，怪不得看起来老了。想当年第一次看到王羽佳的演奏还是在这个古代视频
https://b23.tv/o6E1gtH
https://b23.tv/o6E1gtH
Chips and Cheese
Inside Control Data Corporation’s CDC 6600
#ChipAndCheese
Telegraph | source
(author: clamchowder)
Inside Control Data Corporation’s CDC 6600
#ChipAndCheese
Telegraph | source
(author: clamchowder)
Harry Chen’s Blog
在 Linux 6.6 上使用 Intel DG1 GPU 加速视频编解码
Telegraph | source
(author: Shengqi Chen ([email protected]))
在 Linux 6.6 上使用 Intel DG1 GPU 加速视频编解码
Telegraph | source
(author: Shengqi Chen ([email protected]))
本频道温馨提醒：若遇到疑似诈骗可拨打反诈咨询电话 96110 咨询。若发现上当受骗，请注意及时保存好相关证据，并第一时间拨打 110 报警。
杰哥的{运维，编程，调板子}小笔记
开发一个链接器（2）
前言
这个系列的第一篇博客实现了一个最简单的静态链接器，它可以输入单个 ELF .o 文件，输出 ELF 可执行文件。接下来，我们需要把它升级到支持输入两个或者更多的 ELF .o 文件。
source
开发一个链接器（2）
前言
这个系列的第一篇博客实现了一个最简单的静态链接器，它可以输入单个 ELF .o 文件，输出 ELF 可执行文件。接下来，我们需要把它升级到支持输入两个或者更多的 ELF .o 文件。
source
Arch Linux: Recent news updates
The xz package has been backdoored
TL;DR: Upgrade your systems and container images now!
As many of you may have already read 1, the upstream release tarballs for
This vulnerability is tracked in the Arch Linux security tracker 2.
The
The following release artifacts contain the compromised
● installation medium
● virtual machine images
● container images created between and including 2024-02-24 and 2024-03-28
The affected release artifacts have been removed from our mirrors.
We strongly advise against using affected release artifacts and instead downloading what is currently available as latest version!
Upgrading the system
It is strongly advised to do a full system upgrade right away if your system currently has
Upgrading container images
To figure out if you are using an affected container image, use either
or
depending on whether you use
Any Arch Linux container image older than
Run either
or
to upgrade affected container images to the most recent version.
Afterwards make sure to rebuild any container images based on the affected versions and also inspect any running containers!
Regarding sshd authentication bypass/code execution
From the upstream report 1:
However, out of an abundance of caution, we advise users to remove the malicious code from their system by upgrading either way. This is because other yet-to-be discovered methods to exploit the backdoor could exist.
source
(author: David Runge)
The xz package has been backdoored
TL;DR: Upgrade your systems and container images now!
As many of you may have already read 1, the upstream release tarballs for
xz in version 5.6.0 and 5.6.1 contain malicious code which adds a backdoor.This vulnerability is tracked in the Arch Linux security tracker 2.
The
xz packages prior to version 5.6.1-2 (specifically 5.6.0-1 and 5.6.1-1) contain this backdoor.The following release artifacts contain the compromised
xz:● installation medium
2024.03.01● virtual machine images
20240301.218094 and 20240315.221711● container images created between and including 2024-02-24 and 2024-03-28
The affected release artifacts have been removed from our mirrors.
We strongly advise against using affected release artifacts and instead downloading what is currently available as latest version!
Upgrading the system
It is strongly advised to do a full system upgrade right away if your system currently has
xz version 5.6.0-1 or 5.6.1-1 installed:pacman -SyuUpgrading container images
To figure out if you are using an affected container image, use either
podman image history archlinux/archlinuxor
docker image history archlinux/archlinuxdepending on whether you use
podman or docker.Any Arch Linux container image older than
2024-03-29 and younger than 2024-02-24 is affected.Run either
podman image pull archlinux/archlinuxor
docker image pull archlinux/archlinuxto upgrade affected container images to the most recent version.
Afterwards make sure to rebuild any container images based on the affected versions and also inspect any running containers!
Regarding sshd authentication bypass/code execution
From the upstream report 1:
openssh does not directly use liblzma. However debian and several other distributions patch openssh to support systemd notification, and libsystemd does depend on lzma.Arch does not directly link openssh to liblzma, and thus this attack vector is not possible. You can confirm this by issuing the following command:
ldd "$(command -v sshd)"However, out of an abundance of caution, we advise users to remove the malicious code from their system by upgrading either way. This is because other yet-to-be discovered methods to exploit the backdoor could exist.
source
(author: David Runge)
